# VisQualdex: a comprehensive guide to good data visualization

Jan Sawicki  ORCID: 0000-0002-8930-7564, Warsaw University of Technology,
<EMAIL_ADDRESS>Michał Burdukiewicz  ORCID: 0000-0001-8926-582X,
Institute of Biotechnology and Biomedicine, Autonomous University of Barcelona
<EMAIL_ADDRESS>
###### Abstract

The rapid influx of low-quality data visualizations is one of the main
challenges in today’s communication. Misleading, unreadable, or confusing
visualizations spread misinformation. Furthermore, they fail to deliver their
message to the viewer. The scale of the problem is big enough that there
already exist public fora gathering tens of thousands of users criticizing
graphics and charts (reddit.com/r/dataisugly) made with obvious mistakes.
Current attempts at data visualization appear mostly as simple and
overgeneralized checklists, and often lack systematicity and versatility. The
lack of proper tooling for evaluating data visualization quality further
heightens the problem.

Therefore, this paper proposes VisQualdex, a systematic set of guidelines for
static data visualization. The codex categorization is based and inspired by
the theory of Grammar of Graphics. It contains dozens of criteria designed to
catch various errors and mistakes of different categories and magnitude.
Furthermore, it has been peer-reviewed and tested by experts of data
visualization, data science, graphics design, information technology and
computer science.

To apply theory in the real world and increase the practical impact of
VisQualdex, this contribution also introduces a practical tool. The
implementation of the guidelines is available in the form of the web server,
https://visqual.onrender.com, developed as a single page application in
JavaScript using Vue.js and Material Design principles.

##  1 Introduction

The first historical stamps of data visualization reach back to before 17th
century. Its “golden age” dates to the second half of 19th century [1].
However, it is the 21th that may be called the renaissance of data
visualization.

Human preference to acquire information with visual means [2] in tandem with
the time efficiency of conveying information with charts [3] results in
massive production of data visualization applied in various fields, including
business analysis, Big Data, psychology, journalism, and production process
[4, 5]. Mass-produced charts, graphs, diagrams, schemes and infographics flood
the market and the viewers [6].

The influx of data visualizations is possible thanks to the vast plethora of
specialized tools. Although novel software makes visualization easier, they do
not ensure the quality of their creations. Moreover, no modern tools are
designed to evaluate the quality of the data visualization. We are still
limited to guidelines presented in checklists, lists of questions or
suggestions that often fail to fulfill their task [7] . To fill this void, we
propose organized, systematic data visualization guidelines based on state-of-
the-art practices, VisQualdex.

Our methodology allows everyone, from non-specialists to data science experts,
to assess the quality of data visualization and pinpoint existing problems.
Compared to current methods for data visualization evaluation, VisQualdex
leads to a more exhaustive and complete evaluation, due to utilizing a
systematic, precise and scientifically supported criteria. Moreover, the
VisQualdex is also available as the companion web application, VisQual, and
thus can be easily incorporated in many design workflows.

###  1.1 The spectrum of data visualizations

The focus of VisQualdex is to evaluate the quality of broadly understood
static “data visualizations”. The definitions in the literature vary from the
“image that is representative of the raw data” [8] to “the set of methods for
graphically displaying information in a way that is understandable and
straightforward” [9]. Despite the relative vagueness of these definitions,
they capture the essential aim of the data visualization, which is to
communicate information in a graphical form. The “static” keyword indicated
that this guideline refers to visualization that could be simply printed out
without losing its key features, i.e. interactive dashboard or real 3D
visualization are out of the scope.

In all types of communication, there are many possibilities of conveying the
same message. Therefore, the data visualization itself covers drastically
different entities, ranging from the simple chart (Figure 1) to more complex
visualizations (Figure 2). It provides an additional layer of complication to
the data visualization assessment, as the rules must be general enough to
apply to all types of data visualization.

Figure 1: An example of a “classical” data visualization Figure 2: An example
of a “non-classical” data visualization (adapted from Charles Lallemand’s
“tour de force” nomogram from a work on hexagonal charts [10]

###  1.2 State of the art

Despite the vagueness of definitions, the way we describe data visualizations
is subject to numerous improvements over time [1] . These small steps result
in more structured descriptions of visualizations, exemplified by the grammar
of graphics. These theoretical achievements have contributed to the
development of practical tools such as Matplotlib, Seaborn, Plotly and others
[11, 12, 13, 14].

In a glaring difference, the evaluation of data visualization is still as
unsystematic as it used to be in the past. The first debate on that topic
dated back to 1857 and resulted in several advises [15]. The theoretical
understanding of the correctness of data visualization has grown over time
with new or revised good practices [8] , but very few propose practical and
applicable evaluation methods.

The lack of a systematic approach stems from the popularity of checklists as
one of the most commonly adapted evaluation systems. Here, a checklist is a
list of potential mistakes, sometimes divided in thematic sections. The first
checklists (or guidelines) date back to 1915 [16], but the community of data
visualization practitioners is still producing newer counterparts [17] .

Checklists have two main practical advantages: simplicity and shortness.
Simplicity means that the majority of the state-of-the-art checklists can be
easily operated by any viewer with a basic understanding of the most trivial
data visualization concepts, like chart, axis or scale. Moreover, most
visualization checklists are brief (e.g., about 20 questions [17, 18] ). This
short length, along with the simplicity, translates to a relatively good
assessment pace.

###  1.3 Disadvantages of the checklist usage

However, checklists are characterized by the disorder happening on two
different conceptual levels: the lack of organization and varying levels of
universality.

In the majority of studied examples, checklists do not possess any grouping or
hierarchy of the guidelines. Although some checklists demonstrate some degree
of guideline categorization, they often do not reflect the state-of-art data
visualization descriptions and may have a practical rationale.

The varying level of universality happens when general guidelines (e.g., keep
the graph two-dimensional) occur along with more specific pieces of advice
(e.g., ’use bar charts to visualize achievement of an objective’). It limits
the scope of the checklist to a particular set of data visualizations. This
problem is even more pronounced if the checklist contains a scale based on the
number of questions answered correctly or fulfilled guidelines. In this
situation, non-general guidelines falsely lower the actual score of a
visualization.

Moreover, usage of checklists forces following the state-of-the-art
methodology and logic of checklists [19], which state that (some points are
skipped):

  * •

“The list should be complete (no significant omissions).” and “The checkpoints
should refer to criteria and not mere indicators.”

According to this research, the second rule is most often broken as none of
the state-of-the-art checklists have “complete”/“full” coverage of the
evaluation criteria. As most of both state-of-the-art data visualization
checklists aim at an “engineering” approach, they tend to have very strict,
concise and precise points. However, this causes them to sometimes be
superficial, oversimplified and focus on indicators instead of criteria. For
example, a rule “No more than 3 colors” [18] is focusing purely on indicators,
but disallows great 4-color visualizations from passing the benchmark.
Additionally, a rule “Did you start the Y-axis at 0?” (answer yes/no) [20]
allows only charts which do not cut the axis in a justifiable way (e.g. shoe
sizes for adults, Earth temperatures with Kelvin units, etc.).

  * •

“The criteria should be commensurable.”

This criterion is not applicable to data visualization checklists, because
some mistakes are more significant than others. There exist visualizations
which can follow all criteria except one and still be condemning wrong.

  * •

“The list should be concise (to assist its mnemonic function).”

In contrast to engineering processes or medical applications [21] , data
visualization does not always follow strict regularities as it is a mix of
applied arts and fine arts which cannot be separated [22, 23] .

Therefore, applying checklist format to data visualization evaluation may lead
to problems which are neither the problem of the checklist methodology,
neither the data visualization evaluation. The problem lies in forcefully
fusing the two ideas together.

All problems described above, together with the brevity, result in the non-
exhaustiveness of checklists. Right now, there are no checklists that would
approach the evaluation of data visualization in a systematized way.
Therefore, we have designed VisQualdex to at least partially alleviate these
issues and produce an evaluation methodology applicable to the broad spectrum
of data visualizations.

##  2 Design of VisQualdex

The development of VisQualdex follows the VISupply framework for design of
data visualization guidelines [24]. It covers four main steps:

  * •

Evidence collection
Collection and diligent analysis of research works about data visualization.

  * •

Integration
Curation of existing data visualization guidelines, good practices,
suggestions and similar.

  * •

Contextualization & Generalization
Merging concepts from different works and forming clusters, a.k.a.
“categories” (see section 2.1).

  * •

Guideline Definition
Formalization of VisQualdex, i.e. stating the “question” format, supplementing
missing areas and verifying VisQualdex in practice, utilizing and extending
nomenclatural notions [25] .

Moreover, an original concept introduced in VisQualdex consists of the four
main traits of a correct data visualization. These four pillars of VisQualdex
are:

  1. 1.

Real data instead of guesstimates.

  2. 2.

Clarity and readability instead of incomprehensibility and ambiguity.

  3. 3.

Simplicity and summarization instead of complexity and raw data.

  4. 4.

Guidance and objectivity instead of manipulation and subjectivity.

Finally, the codex has been peer-reviewed by 4 independent reviewers. The
reviewers were experts and specialists in the following fields (parenthesis
contain the reviewer’s higher domain): data visualization (computer science),
data science (computer science), graphics and design (fine arts) and
information technology (computer science). The reviewers all submitted their
critique to all the questions and overall codex design. The feedback was
gathered in 1–3 iterations, depending on the reviewer. All the comments and
suggestions caused various criteria (VisQualdex questions) to be introduced,
redefined or abandoned due to lack of quality evidence.

It is important to note that in some initial stages of development, the tool
was supposed to be based on user testing and feedback in a “wisdom of the
crowds” methodology. However, the user’s feedback was very fragmented and not
unanimous. Moreover, it was highly biased to the user experience. Therefore,
the expert approach was chosen to strengthen the final criteria, maximize the
good practices and minimize the bias of random user evaluation.

###  2.1 Categories

The important part of VisQualdex is the categorization of guidelines. The
baselines are the formalized descriptions of Grammar of Graphics (GoG) [26]
and Layered Grammar of Graphics (LGoG) [27]. Although both of these approaches
constitute an in-depth description of data visualization, they are used
primarily for either building or decomposing the visualization object. As this
is a different goal from the evaluation of data visualizations, GoG and LGoG
are only reference points. Therefore, VisQualdex utilizes a redesigned
categorization of guidelines. Furthermore, proposed categories are complete
(i.e. there is no “others” category) and disjoint (i.e. each of the questions
belongs exactly to one category).

Subjective
The objective of this category is to incorporate any purely subjective aspects
of the visualization. Although all categories concern issues that may be
answered differently depending on the viewer, this one focuses on things
exclusively related to the opinion of the on-looker.

Theme
This category contains all visual features and artistic choices not directly
depending on data, like colors (not related to the color scale), fonts,
spacing, and any additional graphics that are not strictly part of the chart.

Coordinates
This category is responsible for the coordinate system and units. Its purpose
is to check if all coordinates systems (or their alternatives), units and axes
are correctly prepared, provided and presented. It also examines if the
relation between shear data and all the aspects above is consistent.

Geometry
This category includes all information about the shapes used for data
presentations (e.g., the shape itself and its dimensions). It concerns the
shape of the whole figure as well as all used figures and any other
geometrical aspects.

Guides
This category handles any text content that appears on the visualization. It
focuses only on the content, not the display of e.g., title, legend, axes
labels, additional comments, labels etc. It verifies the most importantly the
content of the text but also its clarity, objectivity and overall necessity.

Perception
This category focuses on the general perception of the data. It is also
responsible for detecting all misuses leading to the incorrect understanding
of the data, e.g., bar charts with bars starting at an arbitrary point to make
the difference between bar length more pronounced.

Data
This category is responsible for evaluating issues related only to data and
all the possible issues such as data source/validity, missing data, and
appropriateness of data explanations (e.g., used metrics).

####  2.1.1 Questions

Each category contains questions which represent unitary criteria based on the
pillars described in section 2. The most important features of them are:

  * •

All questions are “yes or no” and trigger (negative answer) only if something
is incorrect.

  * •

Questions do not overlap or include each other.

  * •

All questions address as general issues as possible while focusing on one
particular type of mistake. It means that each can question can be applied to
any visualization regardless of factors such as form, type, content. However,
some categories are incompatible with some visualizations by definition, e.g.,
a simple bar chart without any faceting cannot be evaluated in terms of
faceting.

  * •

It is possible for one general bad practice to trigger many questions

  * •

Depending on the context, a single negative answer may have a tiny or gigantic
impact on the visualization understanding. It means that it is impossible to
judge the quality of a visualization solely by the fraction of positively
answered questions.

  * •

Literature sources support most questions (the complete citations list
available in the supplementary materials).

VisQualdex contains a total of 60 criteria in the form of a question which
address/detect different mistakes. We present their general content in the
form of the word cloud (Figure 3).

Figure 3: Wordcloud displaying most popular words used in questions (without
stopwords)

The full list of questions is available in the supplementary materials. Here,
we present and analyze a few exemplary questions.

Q: "Is there not too many colors representing the data?" In the case of
gradient color scale, the distribution of the colors should be regular. The
figure 4 shows a proper distribution of colors on a gradient scale. Even
though this rule does not touch upon the topic of the choice of colors, it is
worth mentioning that other studies [28] suggest refraining from “rainbow
scale” and advise simpler/fewer color combinations instead.

Figure 4: Example of an equidistributed color gradient scale (using dataset
Iris [29])

Q: "Does it omit or utilize properly the third dimension?", This question
focuses on minimizing the additional dimensional complications of the
visualization. According to state-of-the-art research [30] using more than two
dimensions on a visualization may be misleading and difficult to perceive.
Moreover, another study [31] shows that interpreting angles (which appear a
lot more often on 3D graphics) has many possible vicious implications, ranging
from minor “illusory effects” distorting the viewer perception to completely
hiding some data points on the visualization. See figure 5 for a graphical
example of how differently the same angle (data point) looks due to different
projections.

Figure 5: Example of different angles for a 3D pie chart

Q: "Does the visualization obey the reading gravity?", The concept of reading
gravity [32] comprehensively aggregates all aspects of the order in which the
viewer perceives (reads) the visualization. It accounts for how the user reads
the text of the visualization and in what order they see the data points, sub-
charts (if faceting) and all other visuals. Although most western cultures are
sinistrodextral (i.e. read from left to right) and from top to bottom, some
cultures follow different patterns (e.g., Arabic is written right to left [33]
, Hanunuo script is written bottom to top [34] ). Hence, to maintain
flexibility and universality, the question imposes general “reading gravity”
instead of “left to right, top to bottom”.

##  3 Technical implementation

The VisQualdexhas been implemented as an easy to use online tool for data
evaluation. The tool is hosted at https://visqual.onrender.com and a
screenshot is presented in Figure 6. The tool allows anyone, even without
advanced visualization knowledge, to upload a data evaluation (a picture in
any common format, i.e. JPG, PNG etc.) and evaluate it by going through all
the questions. Each question has a yes or no answer. If a question does not
apply to a particular chart or a user cannot answer a question because they
are unsure, they can skip it, which marks them as “NA” (Not Applicable).
Moreover, most of the questions have examples presenting good or bad practices
of that question. For example, the question “Are colors distinct?” shows a
“bad example” in which the colors are used incorrectly (i.e. continuous color
scale is applied to the categorical axis). After processing all the questions,
a user can see the report with percent of questions answered positively in
each category. The higher the percent, the better the evaluation is. Moreover,
they can download a persistent form of this report to the computer in a JSON
or CSV format.

From the technical point of view, the website is implemented in Vue.js [35] as
a single page application (SPA). Therefore, it does not need to reload the
page at any point. However, it is responsive to changes and intuitive because
it is based on the Material Design [36]. This makes it easy to use for users
without technical knowledge. Additionally, all questions are stored in an
external file, so it is possible to hot swap any content. Finally, the whole
project has been carefully maintained using a version control system, Git
[37].

##  4 Discussion

The field of data visualization does not suffer from the lack of guidelines
and checklists, but rather from their surplus and disorder. This disarray
results in a situation where our checklists are not comprehensive and thus
dismiss the impact of the interaction of many factors determining the
effectiveness of visual communication [38]. VisQualdex is the first codex (a
structured set of criteria) that could be at the same time versatile and
extensive enough to cover all existing data visualizations.

Our systematic approach results in a set of rules that constitutes a
foundation for tools for data visualization creation (e.g., Microsoft Excel,
Plotly, ggplot, Matplotlib, D3, etc.) and instruments for automatic/semi-
automatic data visualization correction (e.g., project ReVision [39]). A
principal example is the usage VisQualdex for default settings of these tools.

One of the problems concerning checklists is a varying level of detail.
Specific points may mention at the same time significantly narrow and very
general criteria while being on the same “level” of evaluation or even share
the evaluation weight. It leads to imbalanced evaluation, which may either
allow “incorrect” visualizations to slip through the metric or “good”
visualizations to be unfairly punished for minor mistakes. VisQualdex
partially solves this problem with categories, which guard question overlap
and thematic division. However, we see it only as one of the first steps into
a comprehensive visualization ontology, focused on the evaluation, instead of
creation [40] .

There are certain aspects of data visualization that could not be included in
questions due to lack of scientific consensus and ongoing heated debate
regarding the right answer. A primary example of it is the question “Is the
data-to-ink ratio rational?”. There are respected experts like Edward Tufte
[41] and others [42, 43] who favor minimalism in data visualization and reject
“chart junk” [44]). There are also respected experts like Alberto Cairo [23]
who claim that “chart junk” can be useful [45] and claim that redundancy
(e.g., highlighting in color) may help to quicker convey the message and
improve memorability [46]. Overly encumbering the visualization with
unnecessary information may lead to confusion, but leaving as little trace of
the information may also turn a visualization into a “clue hunt” instead of
quickening information perception. A similar debate considers the “Y axis
trimming” [47]. There are works claiming the starting the Y axis from 0 is the
best way [48], while others suggest that different ranges apply in different
situations [49]. These and other scientific arguments prove that data
visualization is first a still developing and lively domain and second, that
it is not purely an applied art/exact science but also fine arts/humanities.
Moreover, it also implies that the consensus regarding specific aspects of
visualizing information is still fluid and in future there will be a need to
update the VisQualdex guidelines.

Finally, the current and future techniques of image processing will make it
possible to automate or semi-automate some evaluation steps.

Figure 6: VisQual website screenshot

##  5 Conclusion

The following conclusions emerged from this thorough analysis and after seeing
thousands of graphs, charts or infographics. Data visualization is a field on
the border of computer science, data science and arts [22] , which renders it
highly subjective to the bias of the creator and the viewer. However, we
believe it is possible to forge universal criteria and find a universal
standard to visualize data more understandably. VisQualdex is our first
attempt at this task.

##  Appendix A Supplement

Supplementary materials are in file Supplement 1 - VisQual questions.

## References

  * [1] M. Friendly, “A brief history of data visualization,” in Handbook of data visualization, pp. 15–56, Springer, 2008.
  * [2] J. H. Kaas and P. Balaram, “Current research on the organization and function of the visual system in primates,” // Eye and brain, vol. 6, no. Suppl 1, p. 1, 2014.
  * [3] G. V. R. J. S. Prasad and A. Ojha, “Text, table and graph – which is faster and more accurate to understand?,” in 2012 IEEE Fourth International Conference on Technology for Education, pp. 126–131, 2012.
  * [4] W. Weber and H. Rall, “Data visualization in online journalism and its implications for the production process,” in 2012 16th International Conference on Information Visualisation, pp. 349–356, IEEE, 2012.
  * [5] E. F. Sinar, “Data visualization,” // Big data at work: The data science revolution and organizational psychology, pp. 115–157, 2015.
  * [6] S. Few and P. Edge, “Data visualization: past, present, and future,” // IBM Cognos Innovation Center, 2007.
  * [7] K. Catchpole and S. Russ, “The problem with checklists,” // BMJ Quality & Safety, vol. 24, pp. 545–549, Sept. 2015.
  * [8] T. Azzam, S. Evergreen, A. A. Germuth, and S. J. Kistler, “Data visualization and evaluation,” // New Directions for Evaluation, vol. 2013, no. 139, pp. 7–32, 2013.
  * [9] S. Tonidandel, E. B. King, and J. M. Cortina, Big data at work: The data science revolution and organizational psychology.  Routledge, 2015.
  * [10] C. Lallemand, “Les abaques héxagonaux: Nouvelle méthode générale de calcul graphique, avec de nombreux exemples d’application,” // Ministère des travaux publics, Comité du nivellement général de la France, Paris, 1885.
  * [11] V. Porcu, “Matplotlib,” in Python for Data Mining Quick Syntax Reference, pp. 201–234, Springer, 2018.
  * [12] M. L. Waskom, “Seaborn: statistical data visualization,” // Journal of Open Source Software, vol. 6, no. 60, p. 3021, 2021.
  * [13] H. Wickham, “An introduction to ggplot: An implementation of the grammar of graphics in r,” // Statistics, 2006.
  * [14] S. M. Ali, N. Gupta, G. K. Nayak, and R. K. Lenka, “Big data visualization: Tools and challenges,” in 2016 2nd International Conference on Contemporary Computing and Informatics (IC3I), pp. 656–660, IEEE, 2016.
  * [15] G. Palsky, “The debate on the standardization of statistical maps and diagrams (1857-1901). elements of the history of graphical semiotics,” // Cybergeo: European Journal of Geography, 1999.
  * [16] “Joint committee on standards for graphic presentation,” // Publications of the American Statistical Association, vol. 14, no. 112, pp. 790–797, 1915\.
  * [17] S. Evergreen and A. K. Emery, “Data visualization checklist,” 2016.
  * [18] B. D. I. Team, “Data visualization checklist,” // Berkley Business Process Management, pp. 1–4, 2020.
  * [19] M. Scriven, “The logic and methodology of checklists,” 2000.
  * [20] D. McKie, “Data visualization checklist.” (http://www.davidmckie.com/infogram-data-visualization-checklist.pdf), accessed 2020.
  * [21] E. Grigg, “Smarter clinical checklists: how to minimize checklist fatigue and maximize clinician performance,” // Anesthesia & Analgesia, vol. 121, no. 2, pp. 570–573, 2015.
  * [22] M. Mirahan-Farag, “Chapter fourteen the segregation of applied arts from fine arts and the status of fashion,” // An Anthology of Philosophical Studies Volume 7, p. 145.
  * [23] A. Cairo, The Functional Art: An introduction to information graphics and visualization.  New Riders, 2012.
  * [24] U. Engelke, A. Abdul-Rahman, and M. Chen, “Visupply: A supply-chain process model for visualization guidelines,” in 2018 International Symposium on Big Data Visual and Immersive Analytics (BDVA), pp. 1–9, IEEE, 2018.
  * [25] A. Diehl, M. Kraus, A. Abdul-Raman, M. El-Assady, B. Bach, R. S. Laramee, D. Keim, and M. Chen, “Studying visualization guidelines according to grounded theory,” // arXiv preprint arXiv:2010.09040, 2020.
  * [26] L. Wilkinson, “The grammar of graphics,” in Handbook of computational statistics, pp. 375–414, Springer, 2012.
  * [27] H. Wickham, “A layered grammar of graphics,” // Journal of Computational and Graphical Statistics, vol. 19, no. 1, pp. 3–28, 2010.
  * [28] B. E. Rogowitz, A. D. Kalvin, A. Pelah, and A. Cohen, “Which trajectories through which perceptually uniform color spaces produce appropriate colors scales for interval data?,” in Color and Imaging Conference, vol. 1999, pp. 321–326, Society for Imaging Science and Technology, 1999.
  * [29] R. A. Fisher, “The use of multiple measurements in taxonomic problems,” // Annals of eugenics, vol. 7, no. 2, pp. 179–188, 1936.
  * [30] E. Bertini, N. Elmqvist, and T. Wischgoll, “Judgment error in pie chart variations,” in Proceedings of the Eurographics/IEEE VGTC conference on visualization: Short papers, pp. 91–95, 2016.
  * [31] W. S. Cleveland and R. McGill, “Graphical perception and graphical methods for analyzing scientific data,” // Science, vol. 229, no. 4716, pp. 828–833, 1985.
  * [32] C. Wheildon, D. Ogilvy, and G. Heard, Type & Layout: Are You Communicating Or Just Making Pretty Shapes.  Kickstarting Business Series, Worsley Press, 2005.
  * [33] T. R. Jordan, A. A. Almabruk, E. A. Gadalla, V. A. McGowan, S. J. White, L. Abedipour, and K. B. Paterson, “Reading direction and the central perceptual span: Evidence from arabic and english,” // Psychonomic bulletin & review, vol. 21, no. 2, pp. 505–511, 2014.
  * [34] Y. J. S. Epo, Discourse analysis of suyot: a Hanunuo-Mangyan folk narrative.  PhD thesis, Citeseer, 2014.
  * [35] V. developers, “Vue.js – the progressive javascript framework v3.0..” (https://vuejs.org/guide/introduction.html), 2014.
  * [36] Google Inc., “Material design lite,” 2015.
  * [37] D. Spinellis, “Git,” // IEEE Software, vol. 29, no. 3, pp. 100–101, 2012\.
  * [38] E. Kandogan and H. Lee, “A grounded theory study on the language of data visualization principles and guidelines,” // Electronic Imaging, vol. 2016, no. 16, pp. 1–9, 2016.
  * [39] M. Savva, N. Kong, A. Chhajta, L. Fei-Fei, M. Agrawala, and J. Heer, “Revision: Automated classification, analysis and redesign of chart images,” in Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, UIST ’11, (New York, NY, USA), p. 393–402, Association for Computing Machinery, 2011.
  * [40] D. J. Duke, K. W. Brodlie, and D. A. Duce, “Building an ontology of visualization,” in IEEE Visualization 2004, pp. 7p–7p, IEEE, 2004.
  * [41] E. R. Tufte, N. H. Goeler, and R. Benson, Envisioning information, vol. 2.  Graphics press Cheshire, CT, 1990.
  * [42] K. McGurgan, Data-ink ratio and task complexity in graph comprehension.  Rochester Institute of Technology, 2015.
  * [43] O. Inbar, N. Tractinsky, and J. Meyer, “Minimalism in information visualization: attitudes towards maximizing the data-ink ratio,” in Proceedings of the 14th European conference on Cognitive ergonomics: invent! explore!, pp. 185–188, 2007.
  * [44] M. A. Gatto, “Making research useful: Current challenges and good practices in data visualisation,” 2015.
  * [45] H. Li and N. Moacdieh, “Is “chart junk” useful? an extended examination of visual embellishment,” in Proceedings of the Human Factors and Ergonomics Society Annual Meeting, vol. 58, pp. 1516–1520, Sage Publications Sage CA: Los Angeles, CA, 2014.
  * [46] S. Bateman, R. L. Mandryk, C. Gutwin, A. Genest, D. McDine, and C. Brooks, “Useful junk? the effects of visual embellishment on comprehension and memorability of charts,” in Proceedings of the SIGCHI conference on human factors in computing systems, pp. 2573–2582, 2010.
  * [47] M. Correll, E. Bertini, and S. Franconeri, “Truncating the y-axis: Threat or menace?,” in Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, pp. 1–12, 2020.
  * [48] L. King, “Preparing better graphs,” // Journal of Public Health and Emergency, vol. 2, no. 1, 2018.
  * [49] J. K. Witt, “Graph construction: An empirical investigation on setting the range of the y-axis,” // Meta-psychology, 2019.


Density functions of periodic sequences]Density functions of periodic sequences of continuous events

1]Olga<EMAIL_ADDRESS>
[1]Vitaliy<EMAIL_ADDRESS>
*[1]Computer Science, University of Liverpool, Ashton street, Liverpool, L69 3BX, UK

Periodic Geometry studies isometry invariants of periodic point sets that are also continuous under perturbations.
The motivations come from periodic crystals whose structures are determined in a rigid form but any minimal cells can discontinuously change due to small noise in measurements.
For any integer $k\geq 0$, the density function of a periodic set $S$ was previously defined as the fractional volume of all $k$-fold intersections (within a minimal cell) of balls that have a variable radius $t$ and centers at all points of $S$.
This paper introduces the density functions for periodic sets of points with different initial radii motivated by atomic radii of chemical elements and by continuous events occupying disjoint intervals in time series.
The contributions are explicit descriptions of the densities for periodic sequences of intervals.
The new densities are strictly stronger and distinguish periodic sequences that have identical densities in the case of zero radii.

[MSC Classification]68U05, 51K05, 51N20, 51F30, 51F20

§ MOTIVATIONS FOR THE DENSITY FUNCTIONS OF PERIODIC SETS

This work substantially extends the previous conference paper [3] in Discrete Geometry and Mathematical Morphology 2022.
The past work explicitly described the density functions for periodic sequences of zero-sized points.
The new work extends these analytic descriptions to periodic sequences whose points have non-negative radii.

The proposed extension to the weighted case is motivated by crystallography and materials chemistry [1] because all chemical elements have different atomic radii.
In dimension 1, the key motivation is the study of periodic time series consisting of continuous and sequential (non-overlapping) events represented by disjoint intervals.
Any such interval $[a,b]\subset\R$ for $a\leq b$ is the one-dimensional ball with the center $\dfrac{a+b}{2}$ and radius $\dfrac{b-a}{2}$.

The point-set representation of periodic crystals is the most fundamental mathematical model for crystalline materials because nuclei of atoms are well-defined physical objects, while chemical bonds are not real sticks or strings but abstractly represent inter-atomic interactions depending on many thresholds for distances and angles.

Since crystal structures are determined in a rigid form, their most practical equivalence is rigid motion (a composition of translations and rotations) or isometry that maintains all inter-point distances and includes also mirror reflections [20].

Now we introduce the key concepts.
Let $\R^n$ be Euclidean space, $\Z$ be the set of all integers.

Illustration of Definition <ref> for the hexagonal lattice.
Left: subregions $U_k(t)$ are covered by $k$ disks for the radii $t=0.25, 0.55, 0.75, 1$.
Right: the densities $\psi_k$ are above the corresponding densigram of
accumulated functions

[a lattice $\La$, a unit cell $U$, a motif $M$, a periodic point set $S=M+\La$]

For any linear basis $ v_1,\dots, v_n$ of $\R^n$, a lattice is $\La=\{\sum\limits_{i=1}^n c_i v_i : c_i\in\Z\}$.
The unit cell $U( v_1,\dots, v_n)=\left\{ \sum\limits_{i=1}^n c_i v_i \vl c_i\in[0,1) \right\}$ is the parallelepiped spanned by the basis above.
A motif $M\subset U$ is any finite set of points $p_1,\dots,p_m\in U$.
A periodic point set [20]
is the Minkowski sum $S=M+\La=\{ u+ v \mid  u\in M,  v\in \La\}$.

In dimension $n=1$, a lattice is defined by any non-zero vector $v\in\R$, any periodic point set $S$ is a periodic sequence $\{p_1,\dots,p_m\}+|v|\Z$ with the period $|v|$ equal to the length of the vector $v$.

[density functions for periodic sets of points with radii]

Let a periodic set $S=\La+M\subset\R^n$ have a unit cell $U$.
For every point $p\in M$, fix a radius $r(p)\geq 0$.
For any integer $k\geq 0$, let $U_k(t)$ be the region within the cell $U$ covered by exactly $k$ closed balls $\bar B(p;r(p)+t)$ for $t\geq 0$ and all  points $p\in M$ and their translations by $\La$.
The $k$-th density function $\psi_k[S](t)=\vol[U_k(t)]/\vol[U]$ is the fractional volume of the $k$-fold intersections of these balls within $U$.

The density $\psi_k[S](t)$ can be interpreted as the probability that a random (uniformly chosen in $U$) point $q$ is at a maximum distance $t$ to exactly $k$ balls with initial radii $r(p)$ and all centers $p\in S$.

For $k=0$, the $0$-th density $\psi_0[S](t)$ measures the fractional volume of the empty space not covered by any expanding balls $\bar B(p;r(p)+t)$

In the simplest case of radii $r(p)=0$, the infinite sequence $\Psi[S]=\{\psi_k(t)\}_{k=0}^{+\infty}$ was called in <cit.> the density fingerprint of a periodic point set $S$.
For $k=1$ and small $t>0$ while all equal-sized balls $\bar B(p;t)$ remain disjoint, the 1st density $\psi_1[S](t)$ increases proportionally to $t^n$ but later reaches a maximum and eventually drops back to $0$ when all points of $\R^n$ are covered of by at least two balls.
See the densities $\psi_k$, $k=0,\dots,8$ for the square and hexagonal lattices  in <cit.>.

The original densities helped find a missing crystal in the Cambridge Structural Database, which was accidentally confused with a slight perturbation (measured at a different temperature) of another crystal (polymorph) with the same chemical composition, see <cit.>.

The new weighted case with radii $r(p)\geq 0$ in Definition <ref> is even more practically important due to different Van der Waals radii, which are individually defined for all chemical elements.

The key advantage of density functions over other isometry invariants of periodic crystals (such as symmetries or conventional representations based on a geometry of a minimal cell) is their continuity under perturbations, see details in section <ref> reviewing the related past work.

The only limitation is the infinite size of densities $\psi_k(t)$ due to the unbounded parameters: integer index $k\geq 0$ and continuous radius $t\geq 0$.

We state the following problem in full generality to motivate future work on these densities.

[computation of $\psi_k$]

Verify if the density functions $\psi_k[S](t)$ from Definition <ref>

can be computed in a polynomial time (in the size $m$ of a motif of $S$) for a fixed dimension $n$.

The main contribution is the full solution of Problem <ref> for $n=1$.
Theorems <ref>, <ref>, <ref>, <ref>, and Corollary <ref> efficiently compute all $\psi_k[S](t)$ depending on infinitely many values of $k$ and $t$.

§ REVIEW OF RELATED PAST WORK

Periodic Geometry was initiated in 2020 by the problem <cit.> to design a computable metric on isometry classes of lattices, which is continuous under perturbations of a lattice basis.

Though a Voronoi domain is combinatorially unstable under perturbations, its geometric shape was used to introduce two continuous metrics <cit.> requiring approximations due to a minimization over infinitely many rotations.

Similar minimizations over rotations or other continuous parameters are required for the complete invariant isosets [2, 4] and density functions, which can be practically computed in low dimensions [16], whose completeness was proved for generic periodic point sets in $\R^3$ <cit.>.
The density fingerprint $\Psi[S]$ turned out to be incomplete <cit.> in the example below.

[periodic sequences $S_{15},Q_{15}\subset\R$]

Widdowson et al. <cit.> discussed homometric sets that can be distinguished by the invariant AMD (Average Minimum Distances) and not by diffraction patterns.
The sequences

S_{15} = \{0,1,3,4,5,7,9,10,12\}+15\Z,\\
Q_{15} = \{0,1,3,4,6,8,9,12,14\}+15\Z
\end{array}$

have the unit cell $[0,15]$ shown as a circle in Fig. <ref>.

Circular versions of the periodic sets $S_{15},Q_{15}$.

These periodic sequences [9] are obtained as Minkowski sums $S_{15}=U+V+15\Z$ and $Q_{15}=U-V+15\Z$ for
$U = \{0, 4, 9\}$, $V = \{0, 1, 3\}$.

For rational-valued periodic sequences, <cit.> proved that $r$-th order invariants (combinations of $r$-factor products) up to $r=6$ are enough to distinguish such sequences up to a shift (a rigid motion of $\R$ without reflections).

The AMD invariant was extended to the Pointwise Distance Distribution (PDD), whose generic completeness <cit.> was proved in any dimension $n\geq 1$.
However there are finite sets in $\R^3$ <cit.> with the same PDD, which were distinguished by more sophisticated distance-based invariants in <cit.>.

The subarea of Lattice Geometry developed continuous parameterizations for the moduli spaces of lattices considered up to isometry in dimension two [13, 7] and three [10, 6].

For 1-periodic sequences of points in $\R^n$, complete isometry invariants with continuous and computable metrics appeared in [12], see
related results for finite clouds of unlabeled points [17, 11].

§ THE 0-TH DENSITY FUNCTION $\PSI_0$

This section proves Theorem <ref> explicitly describing the 0-th density function $\psi_0[S](t)$ for any periodic sequence $S\subset\R$ of disjoint intervals.

For convenience, scale any periodic sequence $S$ to period 1 so that $S$ is given by points $0\leq p_1<\cdots<p_m<1$ with radii $r_1,\dots,r_m$, respectively.
Since the expanding balls in $\R$ are growing intervals, volumes of their intersections linearly change with respect to the variable radius $t$.
Hence any density function $\psi_k(t)$ is piecewise linear and uniquely determined by corner points $(a_j,b_j)$ where the gradient of $\psi_k(t)$ changes.

To prepare the proof of Theorem <ref>, we first consider
Example <ref> for the simple sequence $S$.

[$0$-th density function $\psi_0$]

Let the periodic sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ have three points $p_1=0$, $p_2=\dfrac{1}{3}$, $p_3=\dfrac{1}{2}$ of radii $r_1=\dfrac{1}{12}$, $r_2=0$, $r_3=\dfrac{1}{12}$, respectively.
Fig. <ref> shows each point $p_i$ and its growing interval

$$L_i(t)=[(p_i-r_i)-t,(p_i+r_i)+t] \text{ of the length }2r_i+2t$$

for $i=1,2,3$ in its own color: red, green, blue.

The sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ has the points of weights $\dfrac{1}{12},0,\dfrac{1}{12}$, respectively.
The growing intervals around the red point $0\equiv 1\pmod{1}$, green point $\dfrac{1}{3}$, blue point $\dfrac{1}{2}$ have the same color for various radii $t$, see Examples <ref>, <ref>, <ref>.

By Definition <ref> each density function $\psi_k[S](t)$ measures a fractional length covered by exactly $k$ intervals within the unit cell $[0,1]$.
We periodicaly map the endpoints of each growing interval to the unit cell $[0,1]$.
For instance, the interval $[-\dfrac{1}{12}-t,\dfrac{1}{12}+t]$ of the point $p_1=0\equiv 1\pmod{1}$ maps to the red intervals $[0,\dfrac{1}{12}+t]\cup[\dfrac{11}{12}-t,1]$ shown by solid red lines in Fig. <ref>.
The same image shows the green interval $[\dfrac{1}{3}-t,\dfrac{1}{3}+t]$ by dashed lines and the blue interval $[\dfrac{5}{12}-t,\dfrac{7}{12}+t]$ by dotted lines.

At the moment $t=0$, since the starting intervals are disjoint, they cover the length $l=2(\dfrac{1}{12} + 0 +\dfrac{1}{12})=\dfrac{1}{3}$.
The non-covered part of $[0,1]$ has length $1-\dfrac{1}{3}=\dfrac{2}{3}$.
So the graph of $\psi_0(t)$ at $t=0$ starts from the point $(0,\dfrac{2}{3})$, see Fig. <ref>.

The 0-th density function $\psi_0(t)$ for the 1-period sequence $S$  whose points $0,\dfrac{1}{3},\dfrac{1}{2}$ have radii $\dfrac{1}{12},0,\dfrac{1}{12}$, respectively, see Example <ref>.

At the first critical moment $t=\dfrac{1}{24}$ when the green and blue intervals collide at $p=\dfrac{3}{8}$, only the intervals $[\dfrac{1}{8},\dfrac{7}{24}]\cup[\dfrac{5}{8},\dfrac{7}{8}]$ of total length $\dfrac{5}{12}$ remain uncovered.
Hence $\psi_0(t)$ linearly drops to the point $(\dfrac{1}{12},\dfrac{5}{12})$.

At the next critical moment $t=\dfrac{1}{8}$ when the red and green intervals collide at $p=\dfrac{5}{24}$, only the interval $[\dfrac{17}{24},\dfrac{19}{24}]$ of length $\dfrac{1}{12}$ remain uncovered, so $\psi_0(t)$ continues to $(\dfrac{1}{8},\dfrac{1}{12})$.

The graph of $\psi_0(t)$ finally returns to the $t$-axis at the point $(\dfrac{1}{6},0)$ and remains there for $t\geq \dfrac{1}{6}$.

The piecewise linear behavior of $\psi_0(t)$ can be described by specifying the corner points in Fig. <ref>:

Theorem <ref> extends Example <ref>
to any periodic sequence $S$ and implies that the 0-th density function $\psi_0(t)$ is uniquely determined by the ordered gap lengths between successive intervals.

Let a periodic sequence $S=\{p_1,\dots,p_m\}+\Z$ consist of disjoint intervals with centers $0\leq p_1<\dots<p_m<1$ and radii $r_1,\dots,r_m\geq 0$.
Consider the total length $l=2\sum\limits_{i=1}^m r_i$ and gaps between successive intervals $g_i=(p_{i}-r_{i})-(p_{i-1}+r_{i-1})$, where $i=1,\dots,m$ and $p_{0}=p_m-1$, $r_0=r_m$.
Put the gaps in increasing order: $g_{[1]}\leq g_{[2]}\leq\dots\leq g_{[m]}$.

Then the 0-th density $\psi_0[S](t)$ is piecewise linear with the following (unordered) corner points: $(0,1-l)$ and $\left(\dfrac{g_{[i]}}{2},\; 1-l-\sum\limits_{j=1}^{i-1} g_{[j]}-(m-i+1)g_{[i]}\right)$ for $i=1,\dots,m$, so the last corner is $\left(\dfrac{g_{[m]}}{2},0\right)$.

If any corners are repeated, e.g. when $g_{[i-1]}=g_{[i]}$, these corners are collapsed into one corner.

By Definition <ref> the 0-th density function $\psi_0(t)$ measures the total length of subintervals in the unit cell $[0,1]$ that are not covered by any of the growing intervals $L_i(t)=[p_i-r_i-t,p_i+r_i+t]$, $i=1,\dots,m$.
For $t=0$, since all initial intervals $L_i(0)$ are disjoint, they cover the total length $2\sum\limits_{i=1}^m r_i=l$.

Then the graph of $\psi_0(t)$ at $t=0$ starts from the point $(0,1-l)$.
So $\psi_0(t)$ linearly decreases from the initial value $\psi_0(0)=1-l$ except for $m$ critical values of $t$ where one of the gap intervals $[p_i+r_i+t,p_{i+1}-r_{i+1}-t]$ between successive growing intervals $L_i(t)$ and $L_{i+1}(t)$ shrinks to a point.
These critical radii $t$ are ordered according to the gaps $g_{[1]}\leq g_{[2]}\leq\dots\leq g_{[m]}$.

The first critical radius is $t=\dfrac{1}{2}g_{[1]}$, when a shortest gap interval of the length $g_{[1]}$ is covered by the growing successive intervals.
At this moment $t=\dfrac{1}{2}g_{[1]}$, all $m$ growing intervals $L_i(t)$ have the total length $l+mg_{[1]}$.
Then the 0-th density $\psi_0(t)$ has the first corner points $(0,1-l)$ and $\left(\dfrac{g_{[1]}}{2},1-l-mg_{[1]}\right)$.

The second critical radius is $t=\dfrac{g_{[2]}}{2}$, when all intervals $L_i(t)$ have the total length $l+g_{[1]}+(m-1)g_{[2]}$, i.e. the next corner point is $\left(\dfrac{g_{[2]}}{2},1-l-g_{[1]}-(m-1)g_{[2]}\right)$.
If $g_{[1]}=g_{[2]}$, then both corner points coincide, so $\psi_0(t)$ will continue from the joint corner point.

The above pattern generalizes to the $i$-th critical radius $t=\dfrac{1}{2}g_{[i]}$, when all covered intervals have the total length $\sum\limits_{j=1}^{i-1}g_{[j]}$ (for the fully covered intervals) plus $(m-i+1)g_{[i]}$ (for the still growing intervals).

For the final critical radius $t=\dfrac{g_{[m]}}{2}$, the whole unit cell $[0,1]$ is covered by the grown intervals because $\sum\limits_{j=1}^{m}g_{[j]}=1-l$.
The final corner is $(\dfrac{g_{[m]}}{2},0)$.

Example <ref> applies Theorem <ref> to get $\psi_0$ found for the periodic sequence $S$ in Example <ref>.

[using Theorem <ref>]

The sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ in Example <ref> with points $p_1=0$, $p_2=\dfrac{1}{3}$, $p_3=\dfrac{1}{2}$ of radii $r_1=\dfrac{1}{12}$, $r_2=0$, $r_3=\dfrac{1}{12}$, respectively, has
$l=2(r_1+r_2+r_3)=\dfrac{1}{3}$ and the initial gaps
between successive intervals

Order the gaps:

By Theorem <ref> $\psi_0(t)$ has the corner points

See the graph of the 0-th density $\psi_0(t)$ in Fig. <ref>.

By Theorem <ref> any 0-th density function $\psi_0(t)$ is uniquely determined by the (unordered) set of gap lengths between successive intervals.
Hence we can re-order these intervals without changing $\psi_0(t)$.
For instance, the periodic sequence $Q=\{0,\dfrac{1}{2},\dfrac{2}{3}\}+\Z$ with points $0,\dfrac{1}{2},\dfrac{2}{3}$ of weights $\dfrac{1}{12},\dfrac{1}{12},0$ has the same set ordered gaps $g_{[1]}=\dfrac{1}{12}$, $d_{[2]}=\dfrac{1}{3}$, $d_{[3]}=\dfrac{1}{2}$ as the periodic sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ in Example <ref>.

The above sequences $S,Q$ are related by the mirror reflection $t\mapsto 1-t$.
One can easily construct many non-isometric sequences with $\psi_0[S](t)=\psi_0[Q](t)$.
For any $1\leq i\leq m-3$, the sequences $S_{m,i}=\{0,2,3,\dots,i+2,i+4,i+5,\dots,m+2\}+(m+2)\Z$ have the same interval lengths $d_{[1]}=\dots=d_{[m-2]}=1$, $d_{[m-1]}=d_{[m]}=2$ but are not related by isometry (translations and reflections in $\R$) because the intervals of length 2 are separated by $i-1$ intervals of length 1 in $S_{m,i}$.

§ THE 1ST DENSITY FUNCTION $\PSI_1$

This section proves Theorem <ref> explicitly describing the 1st density $\psi_1[S](t)$ for any periodic sequence $S$ of disjoint intervals.
To prepare the proof of Theorem <ref>,
Example <ref> finds $\psi_1[S]$ for the sequence $S$ from Example <ref>.

The trapezoid functions $\eta_R,\eta_G,\eta_B$ and the 1st density function $\psi_1(t)$ for the 1-period sequence $S$  whose points $0,\dfrac{1}{3},\dfrac{1}{2}$ have radii $\dfrac{1}{12},0,\dfrac{1}{12}$, see Example <ref>.

[$\psi_1$ for $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$]

The 1st density function $\psi_1(t)$ can be obtained as a sum of the three trapezoid functions $\eta_R$, $\eta_G$, $\eta_B$, each measuring the length of a region covered by a single interval of one color, see Fig. <ref>.

At the initial moment $t=0$, the red intervals $[0,\dfrac{1}{12}]\cup[\dfrac{11}{12},1]$ have the total length $\eta_R(0)=\dfrac{1}{6}$.
These red intervals $[0,\dfrac{1}{12}+t]\cup[\dfrac{11}{12}-t,1]$ for $t\in[0,\dfrac{1}{8}]$ grow until they touch the green interval $[\dfrac{7}{24},\dfrac{3}{8}]$ and have the total length $\eta_R(\dfrac{1}{8})=\dfrac{1}{6}+\dfrac{2}{8}=\dfrac{5}{12}$ in the second picture of Fig. <ref>.
So the graph of the red length $\eta_R(t)$ linearly grows with gradient 2 from the point $(0,\dfrac{1}{6})$ to the corner point $(\dfrac{1}{8},\dfrac{5}{12})$.

For $t\in[\dfrac{1}{8},\dfrac{1}{6}]$, the left red interval is shrinking at the same rate (due to the overlapping green interval) as the right red interval continues to grow until $t=\dfrac{1}{6}$, when it touches the blue interval $[\dfrac{1}{4},\dfrac{3}{4}]$.
Hence the graph of $\eta_R(t)$ remains constant for $t\in[\dfrac{1}{8},\dfrac{1}{6}]$ up to the corner point $(\dfrac{1}{6},\dfrac{5}{12})$.

After that, the graph of $\eta_R(t)$ linearly decreases (with gradient $-2$) until all red intervals are fully covered by the green and blue intervals at moment $t=\dfrac{3}{8}$, see the 6th picture in Fig. <ref>.

Hence the trapezoid function $\eta_R$ has the piecewise linear graph through the corner points $(0,\dfrac{1}{6})$, $(\dfrac{1}{8},\dfrac{5}{12})$, $(\dfrac{1}{6},\dfrac{5}{12})$, $(\dfrac{3}{8},0)$.
After that, $\eta_R(t)=0$ remains constant for $t\geq \dfrac{3}{8}$.
Fig. <ref> shows the graphs of $\eta_R,\eta_G,\eta_B$ and $\psi_1=\eta_R+\eta_G+\eta_B$.

Theorem <ref> extends Example <ref>
and proves that any $\psi_1(t)$ is a sum of trapezoid functions whose corners are explicitly described.
We consider any index $i=1,\dots,m$ (of a point $p_i$ or a gap $g_i$) modulo $m$ so that $m+1\equiv 1\pmod{m}$.

Let a periodic sequence $S=\{p_1,\dots,p_m\}+\Z$ consist of disjoint intervals with centers $0\leq p_1<\dots<p_m<1$ and radii $r_1,\dots,r_m\geq 0$, respectively.

Consider the gaps $g_i=(p_{i}-r_{i})-(p_{i-1}+r_{i-1})$,
where $i=1,\dots,m$ and $p_{0}=p_m-1$, $r_0=r_m$.

Then the 1st density
$\psi_1(t)$ is the sum of $m$ trapezoid functions $\eta_{i}$, $i=1,\dots,m$, with the corners
$\left(\dfrac{g_{i}}{2}, g+2r_i\right)$,
$\left(\dfrac{g_{i+1}}{2}, g+2r_i\right)$,

Hence $\psi_1(t)$ is determined by the unordered set of unordered pairs $(g_{i},g_{i+1})$, $i=1,\dots,m$.

The 1st density $\psi_1(t)$ equals the total length of subregions covered by exactly one of the intervals $L_i(t)=[p_i-r_i-t,p_i+r_i+t]$, $i=1,\dots,m$, where all intervals are taken modulo 1 within $[0,1]$.

Hence $\psi_1(t)$ is the sum of the functions $\eta_{1i}$, each measuring the length of the subinterval of $L_i(t)$ not covered by other intervals $L_j(t)$, $j\in\{1,\dots,m\}-\{i\}$.

Since the initial intervals $L_i(0)$ are disjoint, each function $\eta_{1i}(t)$ starts from the value $\eta_{1i}(0)=2r_i$ and linearly grows (with gradient 2) up to $\eta_{i}(\dfrac{1}{2}g)=2r_i+g$, where $g=\min\{g_{i},g_{i+1}\}$, when the growing interval $L_i(t)$ of the length $2r_i+2t=2r_i+g$ touches its closest neighboring interval $L_{i\pm 1}(t)$ with a shortest gap $g$.

If (say) $g_{i}<g_{i+1}$, then the subinterval covered only by $L_i(t)$ is shrinking on the left and is growing at the same rate on the right until $L_i(t)$ touches the growing interval $L_{i+1}(t)$ on the right.
During this growth, when $t$ is between $\dfrac{1}{2}g_{i}$ and $\dfrac{1}{2}g_{i+1}$, the trapezoid function $\eta_{i}(t)=g$ remains constant.

If $g_{i}=g_{i+1}$, this horizontal line collapses to one point in the graph of $\eta_{i}(t)$.
For $t\geq\max\{g_{i},g_{i+1}\}$, the subinterval covered only by $L_i(t)$ is shrinking on both sides until the neighboring intervals $L_{i\pm 1}(t)$ meet at a mid-point between their initial closest endpoints $p_{i-1}+r_{i-1}$ and $p_{i+1}-r_{i+1}$.
This meeting time is $t=\dfrac{1}{2}(p_{i+1}-r_{i+1}-p_{i-1}-r_{i-1}) =\dfrac{1}{2}(g_{i}+2r_i+g_{i+1})$, which is also illustrated by Fig. <ref>.
So the trapezoid function $\eta_{i}$ has the corners
$\left(\dfrac{g_{i}}{2}, 2r_i+g\right)$,
as expected.

The distances $g,s,g'$ between line intervals used in the proofs of Theorems <ref> and <ref>, shown here for $k=3$.

Example <ref> applies Theorem <ref> to get $\psi_1$ found for the periodic sequence $S$ in Example <ref>.

[using Theorem <ref> for $\psi_1$]

The sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ in Example <ref> with points $p_1=0$, $p_2=\dfrac{1}{3}$, $p_3=\dfrac{1}{2}$ of radii $r_1=\dfrac{1}{12}$, $r_2=0$, $r_3=\dfrac{1}{12}$, respectively, has
the initial gaps between successive intervals
$g_3=\dfrac{1}{12}$, see all the computations in Example <ref>.

Case (R).
In Theorem <ref> for the trapezoid function $\eta_R=\eta_1$ measuring the fractional length covered only by the red interval, we set $k=1$ and $i=1$.
Then $r_i=\dfrac{1}{12}$, $g_i=\dfrac{1}{3}$ and $g_{i+1}=\dfrac{1}{4}$, so

$g=\min\{g_i,g_{i+1}\}=\dfrac{1}{4}$, $g+2r_i=\dfrac{1}{4}+\dfrac{2}{12}=\dfrac{5}{12}$.

Then $\eta_{R}=\eta_{1}$ has the following corner points:

\left(0,2r_i\right)=\left(0,\dfrac{1}{6}\right), \quad
\left(\dfrac{g_{i}}{2},g+2r_i\right)=\left(\dfrac{1}{6},\dfrac{5}{12}\right), \\ \\
\left(\dfrac{g_{i+1}}{2},g+2r_i\right)=\left(\dfrac{1}{8},\dfrac{5}{12}\right), \\ \\
\left(\dfrac{g_{i}+g_{i+1}}{2}+r_i,0\right)=\left(\dfrac{3}{8},0\right),
\end{array}$$

where the two middle corners are accidentally swapped due to $g_i>g_{i+1}$ but they define the same trapezoid function as in the first picture of Fig. <ref>.

Case (G).
In Theorem <ref> for the trapezoid function $\eta_G=\eta_2$ measuring the fractional length covered only by the green interval, we set $k=1$ and $i=2$.
Then $r_i=0$, $g_i=\dfrac{1}{4}$ and $g_{i+1}=\dfrac{1}{12}$, so

$g=\min\{g_i,g_{i+1}\}=\dfrac{1}{12}$, $g+2r_i=\dfrac{1}{12}+0=\dfrac{1}{12}$.

Then $\eta_{G}=\eta_{2}$ has the following corner points
exactly as shown in the second picture of Fig. <ref>:

\left(0,2r_i\right)=\left(0,0\right), \quad
\left(\dfrac{g_{i}}{2},g+2r_i\right)=\left(\dfrac{1}{8},\dfrac{1}{12}\right), \\ \\
\left(\dfrac{g_{i+1}}{2},g+2r_i\right)=\left(\dfrac{1}{24},\dfrac{5}{12}\right), \\ \\
\left(\dfrac{g_{i}+g_{i+1}}{2}+r_i,0\right)=\left(\dfrac{1}{6},0\right).
\end{array}$$

Case (B).
In Theorem <ref> for the trapezoid function $\eta_B=\eta_3$ measuring the fractional length covered only by the blue interval, we set $k=1$ and $i=3$.
Then $r_i=\dfrac{1}{12}$, $g_i=\dfrac{1}{12}$ and $g_{i+1}=\dfrac{1}{3}$, so

$g=\min\{g_i,g_{i+1}\}=\dfrac{1}{12}$, $g+2r_i=\dfrac{1}{12}+\dfrac{2}{12}=\dfrac{1}{4}$.

Then $\eta_{B}=\eta_{3}$ has the following corner points:

\left(0,2r_i\right)=\left(0,\dfrac{1}{6}\right), \quad
\left(\dfrac{g_{i}}{2},g+2r_i\right)=\left(\dfrac{1}{24},\dfrac{1}{4}\right), \\ \\
\left(\dfrac{g_{i+1}}{2},g+2r_i\right)=\left(\dfrac{1}{6},\dfrac{1}{4}\right), \\ \\
\left(\dfrac{g_{i}+g_{i+1}}{2}+r_i,0\right)=\left(\dfrac{7}{24},0\right)
\end{array}$$

exactly as shown in the third picture of Fig. <ref>.

§ HIGHER DENSITY FUNCTIONS $\PSI_K$

This section proves Theorem <ref> describing the $k$-th density function $\psi_k[S](t)$ for any $k\geq 2$ and a periodic sequence $S$ of disjoint intervals.

To prepare the proof of Theorem <ref>,
Example <ref> computes $\psi_2[S]$ for $S$ from Example <ref>.

[$\psi_2$ for $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$]

The density $\psi_2(t)$ can be found as the sum of the trapezoid functions $\eta_{GB},\eta_{BR},\eta_{RG}$, each measuring the length of a double intersection, see Fig. <ref>.

For the green interval $[\dfrac{1}{3}-t,\dfrac{1}{3}+t]$ and the blue interval $[\dfrac{5}{12}-t,\dfrac{7}{12}+t]$, the graph of the function $\eta_{GB}(t)$ is piecewise linear and starts at the point $(\dfrac{1}{24},0)$ because these intervals touch at $t=\dfrac{1}{24}$.

The green-blue intersection $[\dfrac{5}{12}-t,\dfrac{1}{3}+t]$ grows until $t=\dfrac{1}{6}$, when the resulting interval $[\dfrac{1}{4},\dfrac{1}{2}]$ touches the red interval on the left.
At the same time, the graph of $\eta_{GB}(t)$ is linearly growing (with gradient 2) to the corner $(\dfrac{1}{6},\dfrac{1}{4})$, see Fig, <ref>.

The trapezoid functions $\eta_{GB},\eta_{BR},\eta_{RG}$ and the 2nd density function $\psi_2(t)$ for the 1-period sequence $S$ whose points $0,\dfrac{1}{3},\dfrac{1}{2}$ have radii $\dfrac{1}{12},0,\dfrac{1}{12}$, see Example <ref>.

For $t\in[\dfrac{1}{6},\dfrac{7}{24}]$, the green-blue intersection interval becomes shorter on the left, but grows at the same rate on the right until $t=\dfrac{7}{24}$ when $[\dfrac{1}{8},\dfrac{5}{8}]$ touches the red interval $[\dfrac{5}{8},1]$ on the right, see the 5th picture in Fig. <ref>.
So the graph of $\eta_{GB}(t)$ remains constant up to the point $(\dfrac{7}{24},\dfrac{1}{4})$.

For $t\in[\dfrac{7}{24},\dfrac{5}{12}]$ the green-blue intersection interval is shortening from both sides.
So the graph of $\eta_{GB}(t)$ linearly decreases (with gradient $-2$) and returns to the $t$-axis at the corner $(\dfrac{5}{12},0)$, then remains constant $\eta_{GB}(t)=0$ for $t\geq \dfrac{5}{12}$.

Fig. <ref> shows all trapezoid functions for double intersections and $\psi_2=\eta_{GB}+\eta_{BR}+\eta_{RG}$.

Let a periodic sequence $S=\{p_1,\dots,p_m\}+\Z$ consist of disjoint intervals with centers $0\leq p_1<\dots<p_m<1$ and radii $r_1,\dots,r_m\geq 0$, respectively.
Consider the gaps $g_i=(p_{i}-r_{i})-(p_{i-1}+r_{i-1})$ between the successive intervals of $S$, where $i=1,\dots,m$ and $p_{0}=p_m-1$, $r_0=r_m$.

For $k\geq 2$, the density function $\psi_k(t)$ equals the sum of $m$ trapezoid functions $\eta_{k,i}(t)$, $i=1,\dots,m$, each having the following corner points:

\left(\dfrac{g+s}{2},g\right),
\left(\dfrac{s+g'}{2},g\right),
\left(\dfrac{g+s+g'}{2},0\right),$$

$g,g'$ are the minimum and maximum values in the pair $\{g_{i}+2r_i,g_{i+k}+2r_{i+k-1}\}$, and $s=\sum\limits_{j=i+1}^{i+k-1}g_j+2\sum\limits_{j=i+1}^{i+k-2} r_j$,
so $s=g_{i+1}$ for $k=2$.

Hence $\psi_k(t)$ is determined by the unordered set of the ordered tuples $(g,s,g')$, $i=1,\dots,m$.

The $k$-th density function $\psi_k(t)$ measures the total fractional length of $k$-fold intersections among $m$ intervals $L_i(t)=[p_i-r_i-t,p_i+r_i+t]$, $i=1,\dots,m$.
Now we visualize all such intervals $L_i(t)$ in the line $\R$ without mapping them modulo 1 to the unit cell $[0,1]$.

Since all radii $r_i\geq 0$, only $k$ successive intervals can contribute to $k$-fold intersections.

So a $k$-fold intersection of growing intervals emerges only when two intervals $L_i(t)$ and $L_{i+k-1}(t)$ overlap because their intersection should be also covered by all the intermediate intervals $L_i(t),L_{i+1}(t),\dots,L_{i+k-1}(t)$.

Then the density $\psi_k(t)$ equals the sum of the $m$ trapezoid functions $\eta_{k,i}$, $i=1,\dots,m$, each equal to the length of the
$k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ not covered by other intervals.
Then $\eta_{k,i}(t)$ remains 0 until the first critical moment $t$ when
$2t$ equals the distance between the points $p_i+r_i$ and $p_{i+k-1}-r_{i+k-1}$ in $\R$, see Fig. <ref>, so
$2t=\sum\limits_{j=i+1}^{i+k-1}g_j+2\sum\limits_{j=i+1}^{i+k-2} r_j=s$.
Hence $t=\dfrac{s}{2}$ and $(\dfrac{s}{2},0)$ is the first corner point of

At $t=\dfrac{s}{2}$, the interval of the $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ starts expanding on both sides.
Hence $\eta_{k,i}(t)$ starts increasing (with gradient 2) until the $k$-fold intersection touches one of the neighboring intervals $L_{i-1}(t)$ or $L_{i+k}(t)$ on the left or on the right.

The left interval $L_{i-1}(t)$ touches the $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ when
$2t$ equals the distance from $p_{i-1}+r_{i-1}$ (the right endpoint of $L_{i-1}$) to $p_{i+k-1}-r_{i+k-1}$ (the left endpoint of $L_{i+k-1}$), see Fig. <ref>, so

$$2t=\sum\limits_{j=i}^{i+k-1}g_j+2\sum\limits_{j=i}^{i+k-2} r_j=g_{i}+2r_i+s.$$

The right interval $L_{i+k-1}(t')$ touches the $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t')$ when
$2t'$ equals the distance from $p_{i}+r_{i}$ (the right endpoint of $L_{i}$) to $p_{i+k}-r_{i+k}$ (the left endpoint of $L_{i+k}$), see Fig. <ref>, so

$$2t'=\sum\limits_{j=i+1}^{i+k}g_j+2\sum\limits_{j=i+1}^{i+k-1} r_j=s+g_{i+k}+2r_{i+k-1}.$$

If (say) $g_{i}+2r_i=g<g'=g_{i+k}+2r_{i+k-1}$, the $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ first touches $L_{i-1}$ at the earlier moment $t$ before reaching $L_{i+k}(t')$ at the later moment $t'$.
At the earlier moment, $\eta_{k,i}(t)$ equals $2(t-\dfrac{s}{2})=g_i+2r_i=g$ and has the corner $(\dfrac{g+s}{2},g)$.

After that, the $k$-fold intersection is shrinking on the left and is expanding at the same rate on the right.
So the function $\eta_{k,i}(t)=g$ remains constant until the $k$-fold intersection touches the right interval $L_{i+k}(t')$.
At this later moment $t'=\dfrac{s+g_{i+k}}{2}+r_{i+k-1}=g'$, $\eta_{k,i}(t')$ still equals $g$ and has the corner $(\dfrac{s+g'}{2},g)$.

If $g_{i}+2r_i=g'>g=g_{i+k}+2r_{i+k-1}$, the growing intervals $L_{i-1}(t)$ and $L_{i+k-1}(t)$ touch the $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ in the opposite order.
However, the above arguments lead to the same corners $(\dfrac{g+s}{2},g)$ and $(\dfrac{s+g'}{2},g)$ of $\eta_{k,i}(t)$.
If $g=g'$, the two corners collapse to one corner in the graph of $\eta_{k,i}(t)$.

The $k$-fold intersection $\cap_{j=i}^{i+k-1} L_j(t)$ becomes fully covered when the intervals $L_{i-1}(t),L_{i+k}(t)$.
At this moment, $2t$ equals the distance from $p_{i-1}+r_{i-1}$ (the right endpoint of $L_{i-1}$) to $p_{i+k}-r_{i+k}$ (the left endpoint of $L_{i+k}$), see Fig. <ref>, so
$2t=\sum\limits_{j=i}^{i+k}g_j+2\sum\limits_{j=i}^{i+k-1} r_j=g_i+2r_i+s+g_{i+k}+2r_{i+k-1}=g+s+g'.$
The graph of $\eta_{k,i}(t)$ has the final corner $\left(\dfrac{g+s+g'}{2},0\right)$.

Example <ref> applies Theorem <ref> to get $\psi_2$ found for the periodic sequence $S$ in Example <ref>.

[using Theorem <ref> for $\psi_2$]

The sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ in Example <ref> with points $p_1=0$, $p_2=\dfrac{1}{3}$, $p_3=\dfrac{1}{2}$ of radii $r_1=\dfrac{1}{12}$, $r_2=0$, $r_3=\dfrac{1}{12}$, respectively, has
the initial gaps
$g_3=\dfrac{1}{12}$, see Example <ref>.

In Theorem <ref>, the 2nd density function $\psi_2[S](t)$ is expressed as a sum of the trapezoid functions computed via their corners below.

Case (GB).
For the function $\eta_{GB}$ measuring the double intersections of the green and blue intervals centered at $p_2=p_i$ and $p_3=p_{i+k-1}$, we set $k=2$ and $i=2$.
Then we have the radii $r_i=0$ and $r_{i+1}=\dfrac{1}{12}$, the gaps $g_i=\dfrac{1}{4}$, $g_{i+1}=\dfrac{1}{12}$, $g_{i+2}=\dfrac{1}{3}$, and the sum $s=g_{i+1}=\dfrac{1}{12}$.
The pair

has the minimum value $g=\dfrac{1}{4}$ and maximum value $g'=\dfrac{1}{2}$.
Then $\eta_{2,2}[S](t)=\eta_{GB}$ has the following corners as expected in the top picture of Fig. <ref>:

\left(\dfrac{s}{2},0\right)=\left(\dfrac{1}{24},0\right),\\ \\
\left(\dfrac{g+s}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{4}+\dfrac{1}{12}\Big),\dfrac{1}{4}\right)=\left(\dfrac{1}{6},\dfrac{1}{4}\right), \\ \\
\left(\dfrac{s+g'}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{12}+\dfrac{1}{2}\Big),\dfrac{1}{4}\right)=\left(\dfrac{7}{24},\dfrac{1}{4}\right), \\ \\
\Big(\dfrac{g+s+g'}{2},0\Big)
\end{array}$$

Case (BR).
For the trapezoid function $\eta_{BR}$ measuring the double intersections of the blue and red intervals centered at $p_3=p_i$ and $p_1=p_{i+k-1}$, we set $k=2$ and $i=3$.
Then we have the radii $r_i=\dfrac{1}{12}=r_{i+1}$, the gaps $g_i=\dfrac{1}{12}$, $g_{i+1}=\dfrac{1}{3}$, $g_{i+2}=\dfrac{1}{4}$, and $s=g_{i+1}=\dfrac{1}{3}$.
The pair

has the minimum $g=\dfrac{1}{4}$ and maximum $g'=\dfrac{5}{12}$.
Then $\eta_{2,3}[S](t)=\eta_{BR}$ has the following corners as expected in the second picture of Fig. <ref>:

\left(\dfrac{s}{2},0\right)=\left(\dfrac{1}{6},0\right),\\ \\
\left(\dfrac{g+s}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{4}+\dfrac{1}{3}\Big),\dfrac{1}{4}\right)=\left(\dfrac{7}{24},\dfrac{1}{4}\right), \\ \\
\left(\dfrac{s+g'}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{3}+\dfrac{5}{12}\Big),\dfrac{1}{4}\right)=\left(\dfrac{3}{8},\dfrac{1}{4}\right), \\ \\
\Big(\dfrac{g+s+g'}{2},0\Big)
\end{array}$$

Case (RG).
For the trapezoid function $\eta_{RG}$ measuring the double intersections of the red and green intervals centered at $p_1=p_i$ and $p_2=p_{i+k-1}$, we set $k=2$ and $i=1$.
Then we have the radii $r_i=\dfrac{1}{12}$ and $r_{i+1}=0$, the gaps $g_i=\dfrac{1}{3}$, $g_{i+1}=\dfrac{1}{4}$, $g_{i+2}=\dfrac{1}{12}$, and $s=g_{i+1}=\dfrac{1}{4}$.
The pair

has the minimum $g=\dfrac{1}{12}$ and maximum $g'=\dfrac{1}{2}$.
Then $\eta_{2,1}[S](t)=\eta_{RG}$ has the following corners:

\left(\dfrac{s}{2},0\right)=\left(\dfrac{1}{8},0\right),\\ \\
\left(\dfrac{g+s}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{12}+\dfrac{1}{4}\Big),\dfrac{1}{12}\right)=\left(\dfrac{1}{6},\dfrac{1}{12}\right), \\ \\
\left(\dfrac{s+g'}{2},g\right)
=\left(\dfrac{1}{2}\Big(\dfrac{1}{4}+\dfrac{1}{2}\Big),\dfrac{1}{12}\right)=\left(\dfrac{3}{8},\dfrac{1}{12}\right), \\ \\
\Big(\dfrac{g+s+g'}{2},0\Big)
\end{array}$$

as expected in the third picture of Fig. <ref>.

§ PROPERTIES OF NEW DENSITIES

This section proves the periodicity of the sequence $\psi_k$ with respect to the index $k\geq 0$ in Theorem <ref>, which was a bit unexpected from original Definition <ref>.
We start with the simpler example for the familiar 3-point sequence in Fig. <ref>.

The densities $\psi_k$, $k=0,\dots,9$ for the 1-period sequence $S$ whose points $0,\dfrac{1}{3},\dfrac{1}{2}$ have radii $\dfrac{1}{12},0,\dfrac{1}{12}$, respectively.
The densities $\psi_0,\psi_1,\psi_2$ are described in Examples <ref>, <ref>, <ref> and determine all other densities by periodicity in Theorem <ref>.

[periodicity of $\psi_k$ in the index $k$]

Let the periodic sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$ have three points $p_1=0$, $p_2=\dfrac{1}{3}$, $p_3=\dfrac{1}{2}$ of radii $r_1=\dfrac{1}{12}$, $r_2=0$, $r_3=\dfrac{1}{12}$, respectively.
The initial intervals $L_1(0)=[-\frac{1}{12},\frac{1}{12}]$, $L_2(0)=[\frac{1}{3},\frac{1}{3}]$, $L_3(0)=[\frac{5}{12},\frac{7}{12}]$ have the 0-fold intersection measured by $\psi_0(0)=\dfrac{2}{3}$ and the 1-fold intersection measured by $\psi_1(0)=\dfrac{1}{3}$, see Fig. <ref> and <ref>.

By the time $t=\dfrac{1}{2}$ the initial intervals will grow to
The grown intervals at the radius $t=\dfrac{1}{2}$ have the 3-fold intersection $[-\frac{1}{12},\frac{7}{12}]$ of the length $\psi_3(\frac{1}{2})=\dfrac{2}{3}$, which coincides with $\psi_0(0)=\dfrac{2}{3}$.

With the extra interval $L_4(\frac{1}{2})=[\frac{5}{12},\frac{19}{12}]$ centered at $p_4=1$, the 4-fold intersection is $L_1\cap L_2\cap L_3\cap L_4=[\frac{5}{12},\frac{7}{12}]$.

With the extra interval $L_{5}(\frac{1}{2})=[\frac{5}{6},\frac{11}{6}]$ centered at $p_{5}=\dfrac{4}{3}$, the 4-fold intersection $L_2\cap L_3\cap L_4\cap L_5$ is the single point $\dfrac{5}{6}$.

With the extra interval $L_{6}(\frac{1}{2})=[\frac{11}{12},\frac{13}{12}]$ centered at $p_6=\dfrac{3}{2}$, the 4-fold intersection is
$L_3\cap L_4\cap L_5\cap L_6=[\frac{11}{12},\frac{13}{12}]$.
Hence the total length of the 4-fold intersection at $t=\dfrac{1}{2}$ is $\psi_4(\frac{1}{2})=\frac{1}{3}$, which coincides with $\psi_1(0)=\dfrac{1}{3}$.

For the larger $t=1$, the six grown intervals

L_1(1)=\left[-\dfrac{13}{12},\dfrac{13}{12}\right], &
L_2(1)=\left[-\dfrac{2}{3},\dfrac{4}{3}\right], \\ \\
L_3(1)=\left[-\dfrac{7}{12},\dfrac{19}{12}\right], &
L_4(1)=\left[-\dfrac{1}{12},\dfrac{25}{12}\right], \\ \\
L_5(1)=\left[\dfrac{1}{3},\dfrac{7}{3}\right], &
\end{array}$$

have the 6-fold intersection
$\left[\dfrac{5}{12},\dfrac{13}{12}\right]$ of length $\psi_6(1)=\dfrac{2}{3}$ coinciding with $\psi_0(0)=\psi_3(\frac{1}{2})=\dfrac{2}{3}$.

Corollary <ref> proves that the coincidences in Example <ref> are not accidental. The periodicity of $\psi_k$ with respect to $k$ is illustrated by Fig. <ref>.

The density functions $\psi_k[S]$ of a periodic sequence $S=\{p_1,\dots,p_m\}+\Z$ consist of disjoint intervals with centers $0\leq p_1<\dots<p_m<1$ and radii $r_1,\dots,r_m\geq 0$, respectively, satisfy the periodicity
$\psi_{k+m}(t+\frac{1}{2})=\psi_{k}(t)$ for any $k\geq 0$ and $t\geq 0$.

Since the initial intervals are disjoint, for $k\geq 0$, any $(k+m)$-fold intersection involves $k+m$ successive intervals $L_i(t),\dots,L_{i+k+m-1}(t)$ centered around the points of $S$.
Then we can find an interval $[x,x+1]$ covering exactly $m$ of these initial intervals of $S$.

By collapsing $[x,x+1]$ to the point $x$, any $(k+m)$-fold intersection of $k+m$ intervals grown by a radius $r\geq\dfrac{1}{2}$ becomes a $k$-fold intersection of $k$ intervals grown by $t=r-\dfrac{1}{2}$.
Both $k$-fold and $(k+m)$-fold intersections within any unit cell have the same fractional length, so $\psi_{k+m}(t+\frac{1}{2})=\psi_{k}(t)$ for any $t\geq 0$.

The symmetry $\psi_{m-k}(\frac{1}{2}-t)=\psi_k(t)$ for $k=0,\dots,[\frac{m}{2}]$, and $t\in[0,\frac{1}{2}]$ from <cit.> no longer holds for points with different radii.
For example, $\psi_1(t)\neq \psi_2(\frac{1}{2}-t)$ for the periodic sequence $S=\left\{0,\dfrac{1}{3},\dfrac{1}{2}\right\}+\Z$, see Fig. <ref>, <ref>.
If all points have the same radius $r$, <cit.> implies the symmetry after replacing $t$ by $t+2r$.

The main results of [3] implied that all density functions cannot distinguish the non-isometric sequences
$S_{15} = \{0,1,3,4,5,7,9,10,12\}+15\Z$ and $Q_{15} = \{0,1,3,4,6,8,9,12,14\}+15\Z$ of points with zero radii.
Example <ref> shows that the densities for sequences with non-zero radii are strictly stronger and distinguish the sequences $S_{15}\not\cong Q_{15}$.

[$\psi_k$ for $S_{15},Q_{15}$ with neighbor radii]

For any point $p$ in a periodic sequence $S\subset\R$, define its neighbor radius as the half-distance to a closest neighbor of $p$ within the sequence $S$.

This choice of radii respects the isometry in the sense that periodic sequences $S,Q$ with zero-sized radii are isometric if and only if $S,Q$ with neighbor radii are isometric.
Fig. <ref> shows that the densities $\psi_k$ for $k\geq 2$ distinguish the non-isometric sequences $S_{15}$ and $Q_{15}$ scaled down by factor 15 to the unit cell $[0,1]$, see
Example <ref>.

The densities $\psi_k$, $k=0,\dots,10$, distinguish (already for $k\geq 2$) the sequences (scaled down by period $15$) $S_{15} = \{0,1,3,4,5,7,9,10,12\}+15\Z$ (top) and $Q_{15} = \{0,1,3,4,6,8,9,12,14\}+15\Z$ (bottom), where the radius $r_i$ of any point is the half-distance to its closest neighbor.
These sequences with zero radii have identical $\psi_k$ for all $k$, see <cit.>.

Let $S,Q\subset\R$ be periodic sequences with at most $m$ motif points.
For $k\geq 1$, one can draw the graph of the $k$-th density function $\psi_k[S]$ in time $O(m^2)$.
One can check in time $O(m^3)$ if

To draw the graph of $\psi_k[S]$ or evaluate the $k$-th density function $\psi_k[S](t)$ at any radius $t$, we first use the periodicity from Theorem <ref> to reduce $k$ to the range $0,1,\dots,m$.
In time $O(m\log m)$ we put the points from a unit cell $U$ (scaled to $[0,1]$ for convenience) in the increasing (cyclic) order $p_1,\dots,p_m$.
In time $O(m)$ we compute the gaps $g_i=(p_{i}-r_{i})-(p_{i-1}+r_{i-1})$ between successive intervals.

For $k=0$, we put the gaps in the increasing order $g_{[1]}\leq\dots\leq g_{[m]}$ in time $O(m\log m)$.
By Theorem <ref> in time $O(m^2)$, we write down the $O(m)$ corner points whose horizontal coordinates are the critical radii where $\psi_0(t)$ can change its gradient.

We evaluate $\psi_0$ at every critical radius $t$ by summing up the values of $m$ trapezoid functions at $t$, which needs $O(m^2)$ time.
It remains to plot the points at all $O(m)$ critical radii $t$ and connect the successive points by straight lines, so the total time is $O(m^2)$.

For any larger fixed index $k=1,\dots,m$, in time $O(m^2)$ we write down all $O(m)$ corner points from Theorems <ref> and <ref>, which leads to the graph of $\psi_k(t)$ similarly to the above argument for $k=0$.

To decide if the infinite sequences of density functions coincide: $\Psi[S]=\Psi[Q]$, by Theorem <ref> it suffices to check only if $O(m)$ density functions coincide: $\psi_k[S](t)=\psi_k[Q](t)$ for $k=0,1,\dots,[\frac{m}{2}]$.

To check if two piecewise linear functions coincide, it remains to compare their values at all $O(m)$ critical radii $t$ from the corner points in Theorems <ref>, <ref>, <ref>.
Since these values were found in time $O(m^2)$ above, the total time for $k=0,1,\dots,[\frac{m}{2}]$ is $O(m^3)$.

All previous examples show densities with a single local maximum.
However, the new R code [5] helped us discover the opposite examples.

For the periodic sequence $S=\left\{0,\dfrac{1}{8},\dfrac{1}{4},\dfrac{3}{4}\right\}+\Z$ whose all points have radii 0, the 2nd density $\psi_2[S](t)$ has the local minimum at $t=\dfrac{1}{4}$ between two local maxima.

[densities with multiple maxima]

Fig. <ref> shows a simple 4-point sequence $S$ whose 2nd density $\psi_2[S]$ has two local maxima.
Fig. <ref> and <ref> show more complicated sequences whose density functions have more than two maxima.

For the sequence $S=\Big\{0,\dfrac{1}{81},\dfrac{1}{27},\dfrac{1}{9},\dfrac{1}{3}\Big\}+\Z$ whose all points have radii 0, $\psi_2[S]$
equal to the sum of the shown five trapezoid functions has three maxima.

For the sequence $S=\Big\{0,\dfrac{1}{64},\dfrac{1}{16},\dfrac{1}{8},\dfrac{1}{4},\dfrac{3}{4}\Big\}+\Z$ whose all points have radii 0,

$\psi_3[S]$ has 5 local maxima.

§ CONCLUSIONS AND FUTURE WORK

In comparison with the past work [3], the key contributions of this paper are the following.

Definition <ref> extends density functions $\psi_k$ to any periodic sets of points with radii $r_i\geq 0$.

Theorems <ref>, <ref>, <ref> explicitly  describe all $\psi_k$ for any periodic sequence $S$ of points with radii.

The descriptions of $\psi_k$ allowed us to justify the periodicity of $\psi_k$ in Theorem <ref> and a quadratic algorithm computing any $\psi_k$ in Corollary <ref>.

The code [5] helped us distinguish $S_{15}\not\cong Q_{15}$ in Example <ref> and find sequences whose densities have multiple local maxima in Example <ref>.

Here are the open problems for future work.

Verify if density functions $\psi_k[S](t)$ for small values of $k$ distinguish all non-isometric periodic point sets $S\subset\R^n$ at least with radii 0.

Characterize the periodic sequences $S\subset\R$ whose all density functions $\psi_k$ for $k\geq 1$ have a unique local maximum, not as in Example <ref>.

Similar to Theorems <ref>, <ref>, <ref>, analytically describe the density function $\psi_k[S]$ for  periodic point sets $S\subset\R^n$ in higher dimensions $n>1$.

This research was supported by the grants of the UK Engineering Physical Sciences Research Council (EP/R018472/1, EP/X018474/1)

and the Royal Academy of Engineering Industrial Fellowship (IF2122/186) of the last author.
We thank all reviewers

for their time and helpful advice.

[1]
Anosova, O., Kurlin, V.: Introduction to periodic geometry and topology.
arxiv:2103.02749  (2021)

[2]
Anosova, O., Kurlin, V.: An isometry classification of periodic point sets. In:
Lecture Notes in Computer Science (Proceedings of DGMM). vol. 12708, pp.
229–241 (2021)

[3]
Anosova, O., Kurlin, V.: Density functions of periodic sequences. In: Lecture
Notes in Computer Science (Proceedings of DGMM). vol. 13493, pp. 395–408

[4]
Anosova, O., Kurlin, V.: Recognition of near-duplicate periodic patterns in
polynomial time. arxiv:2205.15298  (2022)

[5]
Anosova, O.: R code for density functions of periodic sequences (2023),

[6]
Bright, M., Cooper, A.I., Kurlin, V.: Welcome to a continuous world of
3-dimensional lattices. arxiv:2109.11538  (2021)

[7]
Bright, M., Cooper, A.I., Kurlin, V.: Geographic-style maps for 2-dimensional
lattices. Acta Crystallographica Section A  79(1),  1–13 (2023)

[8]
Edelsbrunner, H., Heiss, T., Kurlin, V., Smith, P., Wintraecken, M.: The
density fingerprint of a periodic point set. In: SoCG. vol. 189, pp.
32:1–32:16 (2021)

[9]
Grünbaum, F., Moore, C.: The use of higher-order invariants in the
determination of generalized patterson cyclotomic sets. Acta Cryst. A
51,  310–323 (1995)

[10]
Kurlin, V.: A complete isometry classification of 3D lattices.
arxiv:2201.10543  (2022)

[11]
Kurlin, V.: Computable complete invariants for finite clouds of unlabeled
points. arxiv:2207.08502  (2022),

[12]
Kurlin, V.: Exactly computable and continuous metrics on isometry classes of
finite and 1-periodic sequences. arXiv:2205.04388  (2022),

[13]
Kurlin, V.: Mathematics of 2-dimensional lattices. Foundations of Computational
Mathematics  (2022),

[14]
Mosca, M., Kurlin, V.: Voronoi-based similarity distances between arbitrary
crystal lattices. Crystal Research and Technology  55(5),  1900197

[15]
Pozdnyakov, S., et al.: Incompleteness of atomic structure representations.
Phys. Rev. Let.  125,  166001 (2020)

[16]
Smith, P., Kurlin, V.: A practical algorithm for degree-k Voronoi domains of
three-dimensional periodic point sets. In: Lecture Notes in Computer Science
(Proceedings of ISVC). vol. 13599, pp. 377–391 (2022)

[17]
Smith, P., Kurlin, V.: Families of point sets with identical 1D persistence,.
arxiv:2202.00577  (2022),

[18]
Widdowson, D., Kurlin, V.: Pointwise distance distributions of periodic sets.
arXiv:2108.04798 (version 1)  (2021)

[19]
Widdowson, D., Kurlin, V.: Resolving the data ambiguity for periodic crystals.
Advances in Neural Information Processing Systems (arXiv:2108.04798, v2)
35 (2022),

[20]
Widdowson, D., et al.: Average minimum distances of periodic point sets. MATCH
Comm. Math. Comp. Chemistry  87,  529–559 (2022)

Example <ref> motivates using neighbor radii, which are local isometry invariants of points,
to uniquely reconstruction any periodic sequence $S=\{p_1,\dots,p_m\}$ (initially without radii) from pair of densities $\psi_1,\psi_2$ with generic radii.

Let $S\subset\R$ be a sequence with period 1 and $m$ points $0\leq p_1<\dots<p_m<1$ of radii $r_1,\dots,r_m\geq 0$.
The sequence $S$ is called corner-generic if all non-zero coordinates of the corners of the densities $\psi_k$ in Theorems <ref>, <ref>, <ref>.
are distinct.

Then any corner-generic $S$ can be uniquely reconstructed from the 1st and 2nd density functions $\psi_1[S](t),\psi_2[S](t)$ up to isometry in $\R$.

If $S$ is not necessarily corner-generic but all radii of points are zeros, $S$ can be reconstructed from $\psi_1[S'](t)$, $\psi_2[S'](t)$ for a corner-generic sequence $S'$ with the same points as $S$.

Up to translation and reflection of $\R$, one can assume that $p_1=0<p_2<1=p_{m+1}$.
It suffices to identify $p_2,\dots,p_m\in(0,1)$ and radii $r_1,\dots,r_m$.
By Theorem <ref> the 1st density function $\psi_1[S](t)$ is the sum of the trapezoid functions that have the initial gradient $2$ and the corner points
$\left(\dfrac{g_{i}}{2}, g+2r_i\right)$,
$\left(\dfrac{g_{i+1}}{2}, g+2r_i\right)$,
where $g=\min\{g_{i},g_{i+1}\}$.

Due to a cyclic order of the gaps $g_i=(p_{i}-r_{i})-(p_{i-1}+r_{i-1})$ between successive intervals, one can assume that the minimum gap is $g_1$, so $g=g_1.
For any $0≤t≤g_12$, the function $ψ_1[S](t)$ is linearly increasing with the gradient $2m$.
This gradient drops to $2m-2$ at the first critical radius $t=g_1/2$, which differs from all other larger coordinates $g_i/2$ and $g_i+g_i+1/2$, which are all distinct by the assumption, where the gradient of $ψ_1(t)$ changes.
\smallskip

At the radius $t=g_1/2$, subtracting from $ψ_1(t)$ the contribution $(m-1)(g_1+2r_1)$ from other still growing $m-1$ trapezoid functions, we get the value $d_1+d_2/2$.
Then the first two corners of $ψ_1(t)$ uniquely determine $r_1$ and $g_1$.

So the first corner of $ψ_1(t)$ also determines the length $d_2=p_3-p_2$ of the second inter-point interval after $[p_1,p_2]$ of the length $d_1$, and the third point $p_3=d_1+d_2$.
\smallskip

Since we know both $d_1,d_2$, we can subtract from $ψ_1(t)$ the whole trapezoid function $η(t)$ with the above corners for $i=2$ for all $t∈[0,1]$.
The resulting function $ψ_1(t)$ is the sum of $m-1$ trapezoid functions depending on $m-1$ inter-point distances $d_2,…,d_m$.
We continue analyzing $ψ_1(t)$ by looking at the first corner where its gradient drops from $2m-2$ to $2m-4$, which gives us another pair $(d_i-1,d_i)$ of successive interval lengths, and so on.
Since all distances $d_i$ are distinct, the above pairs uniquely determine the ordered sequence $d_1,…,d_m$ of all interval lengths, hence the points $p_2,…,p_m∈(0,1)$ of the sequence $S$.
\end{proof}