Existence, uniqueness, and algorithmic computation of general lilypond systems

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