Vesicle computers: Approximating a Voronoi diagram using Voronoi automata

Irregular arrangements of vesicles filled with excitable and precipitating chemical systems are imitated by Voronoi automata - finite-state machines defined on a planar Voronoi diagram. Every Voronoi cell takes four states: resting, excited, refractory and precipitate. A resting cell excites if it has at least one neighbour in an excited state. The cell precipitates if the ratio of excited cells in its neighbourhood versus the number of neighbours exceeds a certain threshold. To approximate a Voronoi diagram on Voronoi automata we project a planar set onto the automaton lattice, thus cells corresponding to data-points are excited. Excitation waves propagate across the Voronoi automaton, interact with each other and form precipitate at the points of interaction. The configuration of the precipitate represents the edges of an approximated Voronoi diagram. We discover the relationship between the quality of the Voronoi diagram approximation and the precipitation threshold, and demonstrate the feasibility of our model in approximating Voronoi diagrams of arbitrary-shaped objects and in constructing a skeleton of a planar shape.     

The Voronoi diagram for graphs and its application in the Sickle Cell Disease research

We propose using a graph-theoretic data structure, the Voronoi diagram for graphs, for analyzing the structure of biological networks. The Voronoi diagram for graphs (VDG) offers an efficient way to cluster the members of a network based on their distance to a subset of input nodes. We study the distance-based decomposition of the human erythrocyte interactome provided by VDG, seeking to elucidate the influence of sickle cell anemia on the function of the erythrocyte proteins. We also provide an efficient open-source Java package that computes VDG.     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I. Theoretical foundations

In this first installment of a two-part paper, the underlying theory for an algorithm that computes the Voronoi diagram and medial axis of a planar domain bounded by free-form (polynomial or rational) curve segments is presented. An incremental approach to computing the Voronoi diagram is used, wherein a single boundary segment is added to an existing boundary-segment set at each step. The introduction of each new segment entails modifying the Voronoi regions of the existing boundary segments, and constructing the Voronoi region of the new segment. We accomplish this by (i) computing the bisector of the new segment with each of the current boundary segments; (ii) updating the Voronoi regions of the current boundary segments by partitioning them with these bisectors; and (iii) constructing the Voronoi region of the new segment as a union of regions obtained from the partitioning in (ii). When all boundary segments are included, and their Voronoi regions have been constructed, the Voronoi diagram of the boundary is obtained as the union of the Voronoi polygons for each boundary segment. To construct the medial axis of a planar domain, we first compute the Voronoi diagram of its boundary. The medial axis is then obtained from the Voronoi diagram by (i) removing certain edges of the Voronoi diagram that do not belong to the medial axis, and (ii) adding certain edges that do belong to the medial axis but are absent from the Voronoi diagram; unambiguous characterizations for edges in both these categories are given. Details of algorithms based on this theory are deferred to the second installment of this two-part paper.     

The One-Round Voronoi Game

In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the fraction of the area of Q occupied by the regions of the points of B in the Voronoi diagram of W \cup B. We give a (randomized) strategy for the second player that always guarantees him a payoff of at least &frac; + , for a constant > 0 and every large enough n. This contrasts with the one-dimensional situation, with Q=[0,1], where the first player can always win more than &frac;.     

Integrability and closest approximation representations

Summary Suppose U is a set,F is a field of subsets of U, andp _AB is the set of all real-valued bounded finitely additive functions defined onF. This paper consists of two main parts. In the first, a previously given (seeRiv. Math. Univ. Parma, (3),2 (1973), pp. 251–276) notion of a subset ofp _AB defined by certain closure properties and called a C-set, is considered, and those C-sets that are linear spaces are characterized. Now, suppose γ is a function whose domain isF and whose range is a collection of number sets with bounded union. The set,J _γ, of all elements ofp _AB with respect to which γ is integrable, for refinements of subdivisions, is a C-set and a linear space (seeRend. Sem. Mat. Univ. Padova,52 (1974), pp. 1–24). The second part of this paper concerns, for μ inp _AB and nonnegative-valued, a representation of the element ofJ _γ closest to μ with respect to variation norm. Entrata in Redazione il 14 giugno 1977.     

The extendible cell method for closest point problems

The extendible cell method is an application of order preserving extendible hashing to multidimensional point files. We derive some of its performance characteristics and show its expected case optimality for closest point problems.     

The Voronoi Diagram of Curved Objects

Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a “well-behaved” Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n).     

Voronoi diagrams and arrangements

We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR ^d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.     

Mathematics education research embracing arts and sciences

As a young field in its own right (unlike the ancient discipline of mathematics), mathematics education research has been eclectic in drawing upon the established knowledge bases and methodologies of other fields. Psychology served as an early model for a paradigm that valorized psychometric research, largely based in the theoretical frameworks of cognitive science. More recently, with the recognition of the need for sociocultural theories, because mathematics is generally learned in social groups, sociology and anthropology have contributed to methodologies that gradually moved away from psychometrics towards qualitative methods that sought a deeper understanding of issues involved. The emergent perspective struck a balance between research on individual learning (including learners’ beliefs and affect) and the dynamics of classroom mathematical practices. Now, as the field matures, the value of both quantitative and qualitative methods is acknowledged, and these are frequently combined in research that uses mixed methods, sometimes taking the form of design experiments or multi-tiered teaching experiments. Creativity and rigor are required in all mathematics education research, thus it is argued in this paper, using examples, that characteristics of both the arts and the sciences are implicated in this work.     

The Voronoi Identity via the Laplace Transform

The classical Voronoi identity $$\Delta (x) = - \frac{2}{\pi }\sum\limits_{n = 1}^\infty {d(n)} \left( {\frac{x}{n}} \right)^{1/2} \left( {K_1 (4\pi \sqrt {xn} ) + \frac{\pi }{2}Y_1 (4\pi \sqrt {xn} )} \right)$$ is proved in a relatively simple way by the use of the Laplace transform. Here Δ(x) denotes the error term in the Dirichlet divisor problem, d(n) is the number of divisors of n and K_1, Y_1 are the Bessel functions. The method of proof may be used to yield other identities similar to Voronoi's.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Free and nonfree Voronoi polyhedra

The Voronoi polyhedron of some point v of a translation lattice is the closure of the set of points in space that are closer to v than to any other lattice points. Voronoi polyhedra are a special case of parallelohedra, i.e., polyhedra whose parallel translates can fill the entire space without gaps and common interior points. The Minkowski sum of a parallelohedron with a segment is not always a parallelohedron. A parallelohedron P is said to be free along a vector e if the sum of P with a segment of the line spanned by e is a parallelohedron. We prove a theorem stating that if the Voronoi polyhedron P _v (f) of a quadratic form f is free along some vector, then the Voronoi polyhedron P _v (g) of each form g lying in the closure of the L-domain of f is also free along some vector. For the dual root lattice E ₆*, and the infinite series of lattices D _2m ⁺ , m ≥ 4, we prove that their Voronoi polyhedra are nonfree in all directions.     

The furthest-site geodesic voronoi diagram

We present anO((n+k) log(n+k))-time,O(n+k)-space algorithm for computing the furthest-site Voronoi diagram ofk point sites with respect to the geodesic metric within a simplen-sided polygon.A preliminary version of this paper appeared in theProceedings of the Fourth ACM Symposium on Computational Geometry, 1988. The work of Boris Aronov was supported by an AT&T Bell Laboratories Ph.D. Scholarship. Part of the work was performed while he was at AT&T Bell Laboratories, Murray Hill, NJ, USA. His current address is Computer Science Department, Polytechnic University, Brooklyn, NY 11201, USA.