Premium
Existence, uniqueness, and algorithmic computation of general lilypond systems
Author(s) -
Heveling Matthias,
Last Günter
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20099
Subject(s) - uniqueness , ball (mathematics) , unit sphere , computation , mathematics , euclidean space , euclidean geometry , metric space , finite set , point (geometry) , discrete mathematics , pure mathematics , algorithm , mathematical analysis , geometry
The lilypond system based on a locally finite subset φ of the Euclidean space ℝ n is defined as follows. At time 0 every point of φ starts growing with unit speed in all directions to form a system of balls in which any particular ball ceases its growth at the instant that it collides with another ball. Based on a more formal definition of lilypond systems given in 1, we will prove that these systems exist and are uniquely determined. Our approach applies to the far more general setting, where φ is a locally finite subset of some space equipped with a pseudo‐metric d . We will also derive an algorithm approximating the system with at least linearly decreasing error. Several examples will illustrate our general results. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006