stolfi@magic.DEC.COM (Jorge Stolfi) (08/22/86)
In article <788@aicchi.UUCP> rns@aicchi.UUCP (Schreiner) asks: > > Does anyone know of a reference to "voronoi diagrams". Glad you asked. Here are more references than you probably will ever want. Sorry for not roting them by relevance, but my computer is going down in a few minutes. Enjoy... --------------------------------------------------- %N = GS-100 %A = {Brassel, K. E., and Reif, D.} %T = {A procedure to generate Thiessen polygons.} %P = {Geographical Analysis Vol. 11 N. 3 (July 1979) 289--303} %R = {Incremental construction preceded by $x$-sort. Empirical tests seem to indicate $O(n^{6/5})$ behavior for u.d. random points; worst case is probably $O(n^2)$. Historical overview of Voronoi diagrams is succint but comprehensive.} %K = {Voronoi diagram, empirical analysis.} --------------------------------------------------- %N = GS-104 %A = {Brostow, W., Dussault, J.-P., and Fox, B. L.} %T = {Construction of Voronoi polyhedra.} %P = {Journal of Computational Phisics, Vol. 29 (1978), 81--92} %R = {Physicist's view of three-dimensional Voronoi. Iterative algorithm. To compute the Delaunay neighbors and the Voronoi region of a site $p_i$, enumerate the other sites by increasing distance from $p_i$. For each $p_j$ in that list, check if the bisector of $p_i$ and $p_j$ intersects the Voronoi region determined by the previous sites on the list. If it does, then add $p_j$ to the Delaunay neighbors of $p_i$, otherwise ignore $p_j$. The sorting guarantees that none of the previously found neighbors will have to be discarded. This is yet another $O(n\log n)$ algorithm for the intersection of $n$ half-planes; the total time is therefore $O(n^2\log n)$.\par The paper also notes that Voronoi diagram for a random set of $n$ sites has $O(n)$ size (is this true for any fixed dimension?). Suggests also that Gabriel graphs are more economical than Delaunay (how much more? what about relative neighborhood graphs?). Interesting.} %K = {Voronoi diagram, Delaunay diagram, Gabriel graph, iterative algorithm, average-case analysis.} --------------------------------------------------- %N = GS-106 %A = {Brown, K. Q.} %T = {Voronoi diagrams from convex hulls.} %P = {Information Processing Letters Vol. 9 No. 5 (December 1979), 223--228.} %R = {Establishes connection between Voronoi diagrams in $\reals^d$ and convex hull of $n$ points on $\sphere_d\subset \reals^{d+1}$. Does it by spherical inversion.} %K = {Voronoi diagram, Delaunay diagram, convex hull, convex polyhedra, higher dimensions.} --------------------------------------------------- %N = GS-180 %A = {Delaunay, B.} %T = {Sur la sph\`ere vide.} %P = {Bull. Acad. Science USSR VII: Class. Sci. Mat. Nat. (1934), 793--800.} --------------------------------------------------- %N = GS-202 %A = {Dwyer, R. A.} %T = {A simple divide-and-conquer algorithm for computing Delaunay triangulations in $O(n \log \log n)$ expected time.} %P = {Proceedings of the 2nd Annual ACM Symposium on Computational Geometry (June 1986), 276--284.} --------------------------------------------------- %N = GS-236 %A = {Edelsbrunner, H., and Seidel, R.} %T = {Voronoi diagrams and arrangements.} %P = {Discrete and Computational Geometry Vol. 1 (1986), 25--44. Also Proceedings of an ACM Conference (STOC? SCG? 1985), 251--261. Also technical report 85-669, CS Department, Cornell University (March 1985).} --------------------------------------------------- %N = GS-263 %A = {Fortune, S.} %T = {A sweepline algorithm for Voronoi diagrams.} %P = {Proceedings of the 2nd Annual ACM Symposium on Computational Geometry (June 1986), 313--322.} --------------------------------------------------- %N = GS-269 %A = {Franklin, W. R., Akman, V., and Verrilli, C.} %T = {Voronoi diagrams with barriers and on polyhedra.} %P = {Typescript. Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute (November 1983).} --------------------------------------------------- %N = GS-27 %A = {Aurenhammer, F.} %T = {Efficient computation of low-order Voronoi diagrams via convex hulls.} %P = {Laserscript, Institut f\"ur Informationsverarbeitung, Graz Technical University, Austria (date unknown; 1985?).} --------------------------------------------------- %N = GS-28 %A = {Aurenhammer, F., and Edelsbrunner, H.} %T = {An optimal algorithm for constructing the weighted Voronoi diagram in the plane.} %P = {Pattern Recognition Vol. 17 No. 2 (1984), 251--257. Also as report F109, Institut f\"ur Informationsverarbeitung, Technical University of Graz (Austria, January 1983).} %K = {Voronoi diagram, weighted Voronoi diagram, polyhedra, subdivisions, halfspace intersection, point location, higher dimensions, convex polyhedra, stereographic projection.} --------------------------------------------------- %N = GS-316 %A = {Guibas, L. J. and Stolfi, J.} %T = {Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.} %P = {ACM Transactions on Graphics Vol. 4 No. 2 (April 1985), 74--123. Also in Proceedings of the 15th STOC --- Annual ACM Symposium on Theory of Computing (April 1983), 221-234.} --------------------------------------------------- %N = GS-33 %A = {Avis, D.} %T = {A survey of heuristics for the weighted matching problem.} %P = {Tech. Rep. SOCS-82.4, School of Computer Science, McGill Univ. (February 1982)} %R = {Survey of heuristics for near-optimal solutions to the Euclidean matching problem in the plane.} %K = {Euclidean matching, lower bounds, average case analysis, Delaunay triangulation.} --------------------------------------------------- %N = GS-330 %A = {Hermeline, F.} %T = {Triangulation automatique d'un poly\`edre en dimension $N$.} %P = {R.A.I.R.O. Analyse Num\'erique Vol. 16 No. 3 (1982) 211--242} %R = {Triangulation of polyhedrons in $n$ dimensions, using the Delaunay triangulation. Some theoretical discussion. Not clear what he does with polyhedrons that can't be triangulated.} --------------------------------------------------- %N = GS-349 %A = {Hwang, F. K.} %T = {An $O(n \log n)$ algorithm for rectilinear minimal spanning trees.} %P = {J. of the ACM Vol. 26, 177--182 (1979)} %R = {L1 Voronoi and MST.} --------------------------------------------------- %N = GS-36 %A = {Avis, D., and Bhattacharya, B. K.} %T = {Algorithms for computing $d$-dimensional Voronoi diagrams and their duals.} %P = {Tech. Rep. SOCS-82.5, School of Computer Science, McGill Univ. (February 1982)} %R = {Computes the Voronoi diagram (by brute force?) in $O(dn^{\lceil d/2\rceil+1})+O(d^3n^{\lceil d/2\rceil}\log n)$ time. Computes the Delaunay by some unrelated technique, with unknown complexity. Observes that the $d$-dimensional Voronoi diagram may have $\omega(n^{\lceil d/2\rceil})$ edges \r[GS-384], while the Delaunay can have at most ${n\choose 2}=O(n^2)$ edges for any $d$; therefore, for $d>4$ the Delaunay may be asymptotically easier to compute than the Voronoi.\par Says a few words on empirical analysis of both algorithms.} %K = {Voronoi diagram, Delaunay diagram, higher dimensions, linear programming, empirical analysis.} --------------------------------------------------- %N = GS-361 %A = {Iri, M., Murota, K., and Ohya, T.} %T = {A fast Voronoi-diagram algorithm with applications to geographical optimization problems.} %P = {Proceedings of the 11th IFIP Conference, Lecture Notes in Control and Information Sciences No. 59, Springer-Verlag (July 1983), 253--288.} --------------------------------------------------- %N = GS-381 %A = {Kirkpatrick, D. G.} %T = {A note on Delaunay and optimal triangulations.} %P = {Information Processing Letters Vol. 10, 127--128 (1980)} %R = {The Delaunay triangulation is not a good approximation to the minimum-weight triangulation of its sites; in fact, it is even worse than what Manacher and Zobrist \r[GS-442] said it was, and for any $n$ there ais a set of $n$ sites whose Delaunay triangulation whose weight is $>(n-1)/5$ times that of the optimal triangulation. In comparison, an arbitrary triangulation of any $n$ sites has weight $<3n/2$ times the optimum.} %K = {Delaunay diagram, minimum-weight triangulation, diameter, convex hull.} --------------------------------------------------- %N = GS-384 %A = {Klee, V.} %T = {On the complexity of $d$-dimensional Voronoi diagrams.} %P = {Archiv der Mathematik Vol. 34 (1980) 75--80} %R = {Establishes lower and upper asymptotic bounds on the maximum number of $k$-dimensional facets in the $d$-dimensional Voronoi diagram of $n$ points (bounds are exact when $k=d-1$). Superseded by \r[GS-569].} %K = {Voronoi diagram, higher dimensions, convex polyhedra.} --------------------------------------------------- %N = GS-394 %A = {Lee, D. T.} %T = {On finding $k$ nearest neighbors in the plane.} %P = {Master thesis UILU-ENG 76-2216. Technical report R-728, Coordinated Science Laboratory, University of Illinois, Urbana (1976).} %R = {Definition, properties and algorithms for the order-$k$ Voronoi diagram of $n$ points in the plane. Shows how to construct the order-$k$ diagram from the order-$(k-1)$ one. As part of the process, shows how to compute the Voronoi diagram of the delaunay neighbors of a site. (Question: does it work also for the vertices of an arbitrary convex polygon?). The algorithm is basically the divide-and-conquer one; although some simplifications can be made due to the particular nature of the sites, the running time is still $O(n\log n)$. The point location algorithm of Lee and Preparata is described, and used to locate a point in the generalized Voronoi.} %K = {Voronoi diagram, closest-point problems, $k$ nearest neighbors, generalized Voronoi diagram, convex polygons, data structures, point location, monotone subdivisions.} --------------------------------------------------- %N = GS-395 %A = {Lee, D. T.} %T = {Proximity and Reachability in the Plane {\rm (Ph. D. Thesis).}} %P = {Rep. R-831, Coordinated Science Lab., Univ. of Illinois, Urbana (Nov. 1978)} %R = {Detailed discussion of Generalized Voronoi algorithms, for general $L_p$ metrics in $O(n\log n)$ time, line segment Voronoi in $O(n\log^2 n)$, Voronoi of a simple polygon in $O(n\log n)$, Voronoi of a set of circles in $O(n\log^2 n)$. Also Generalized Delaunay triangulation (with a given set of ``frozen'' edges) in $O(n\log^2 n)$ time ($O(n\log n)$ if the frozen graph is connected). Mentions Swapping rule, lexicographical ordering, and the InCircle test. Also shortest path between two points with obstacles: $O(n^2\log n)$ for line segments in general position, $O(n^2)$ if a simple polygon, $O(n\log n)$ for parallel line segments.} %K = {Voronoi diagram, line segment Voronoi, circle Voronoi, Voronoi in $L_1$ and $L_\infty$ metrics, triangulation of a simple polygon, Delaunay triangulation, shortest path with obstacles.} --------------------------------------------------- %N = GS-397 %A = {Lee, D. T.} %T = {On $k$-Nearest Neighbor Voronoi Diagrams in the Plane.} %P = {IEEE Trans. on Computers, Vol. C-31 BNo. 6 (Jun. 1982), 478--487} --------------------------------------------------- %N = GS-399 %A = {Lee, D. T.} %T = {Two-dimensional Voronoi diagrams in the $L_p$ Metric} %P = {J. of the ACM Vol. 27, 604--618 (1980)} --------------------------------------------------- %N = GS-401 %A = {Lee, D. T., and Drysdale III, R. L.} %T = {Generalization of Voronoi diagrams in the plane.} %P = {SIAM J. on Computing Vol. 10, 73--87 (1981)} %R = {Voronoi of line segments.} --------------------------------------------------- %N = GS-408 %A = {Lee, D. T., and Schachter, B. J.} %T = {Two Algorithms for constructing the Delaunay Triangulation.} %P = {International J. of Computer and Information Sciences, Vol 9 No. 3 (1980), 219--242.} %R = {Describes the construction of Delaunay diagrams by both the divide-and-conquer and by the incremental method. It thus anticipates much of the Voronoi half of our own paper; however, our presentation and proofs are more detailed. They describe the InCircle test (no formulas, particularized for the case when $prqs$ is a convex quadrilateral) and the swapping rule, attributing them to C. Lawson \r[GS-392], \r[GS-393]. Apparently he introduced them as the means to get a "good" triangulation in the "max-min angle" sense (i.e., one that maximizes the minimum angle of all triangles). Lee and Shachter show that by doing edge swaps while they are applicable, we get the Dealunay triangulation, which has the property of maximizing the "angle signature" (the sequence of the least angle in each face, in increasing order). Some applications: random Delaunay triangulations \r[GS-460], interpolation of functions of two variables \r[GS-455], \r[GS-393], terrain fitting, decomposition of polygons in convex pieces \r[GS-558].} %K = {Delaunay diagram, Voronoi diagram, triangulation of a point set, InCircle test, divide-and-conquer, point location, average-case analysis, subdivisions, polyhedra.} --------------------------------------------------- %N = GS-409 %A = {Lee, D. T., and Wong, C. K.} %T = {Voronoi diagrams in $L_1$ ($L_\infty$) metrics with 2-dimensional storage applications.} %P = {SIAM Journal on Computing Vol. 9 No.1 (February 1980), 200--210. Also IBM Res. Rep. RC 6848 ($\hash$29359), Nov. 1977} --------------------------------------------------- --------------------------------------------------- %N = GS-424 %A = {Lewis, B. A., and Robinson, J. S.} %T = {Triangulation of planar regions with applications.} %P = {The Computer Journal Vol. 21 No. 4 (Date unknown; 1977?), 324--332} %R = {$O(n\log n)$ algorithm for triangulation of a simple polygon witha given set of internal nodes. The basic algorithm is divide-and-conquer: the polygon is broken in two by a polygonal path with vertices on the given nodes, and each part is triangulated separately. After this algorithm finishes, the triangulation is improved by applying an ``heuristic'' which is exactly the Delaunay swapping rule, stated in terms of the minimax angle property!!! Therefore, the result is the Delaunay triangulation of the given polygon and points.\par The splitting step is extremely complex; it is not even clear that it runs in $O(n)$ time. It may improve the convergence of the edge-swapping phase, but it will not affect the result.} %K = {triangulation, triangulation of a simple polygon, Delaunay diagram, Delaunay of a simple polygon, Delaunay minimax property, divide-and-conquer techniques, planar subdivision.} --------------------------------------------------- %N = GS-431 %A = {Lloyd, E. L.} %T = {On triangulations of a set of points in the plane.} %P = {Proc. 18th Annual IEEE Symp. on Foundations of Computer Science (Nov. 1977), 228--240} %R = {Neither greedy nor Delaunay give the minimum length triangulation. To decide if a set of segments contains a triangulation is NP-complete.} --------------------------------------------------- %N = GS-443 %A = {Manacher, G. K., and Zobrist, A. L.} %T = {Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation.} %P = {Information Processing Letters Vol. 9, 31--34 (1979)} %R = {The ratio between the two is unbounded.} --------------------------------------------------- %N = GS-450 %A = {Maus, A.} %T = {Delaunay triangulation and the convex hull of n points in expected linear time.} %P = {BIT Vol. 24 (1984), 151--163.} --------------------------------------------------- %N = GS-455 %A = {McLain, D. H.} %T = {Two dimensional interpolation from random data.} %P = {The Computer Journal Vol. 19 No. 2 (1976), 178--181} %R = {Application of Delaunay triangulation to two-dimensional data fitting. Gives an incremental algorithm for computing the Delaunay, based on the InCircle idea, attributed to Pitteway. At each step, we consider one edge $pq$ on the boundary of the region already triangulated, and find the vertex $r$ for which the circumcenter of $pqr$ is closest to $pq$. Then add the triangle $pqr$ and repeat.\par States (wrongly) that for any point $x$ in a Delaunay triangle, the closest site to $x$ is a vertex of the triangle.\par Gives ALGOL algorithms for computing a line passing through two points and the diastance from a point to that line.} %K = {Delaunay triangulation, incremental algorithms, geometric primitives.} --------------------------------------------------- %N = GS-460 %A = {R. E. Miles} %T = {Solution to problem 67-15 (Probability distribution of a network of triangles).} %P = {SIAM Review Vol. 11 (1969) 399--402.} %R = {Statistical properties of the Delaunay of random points.} --------------------------------------------------- %N = GS-461 %A = {R. E. Miles} %T = {On the homogeneous planar Poisson point-process.} %P = {Math. Biosciences Vol 6. (1970), 85--127.} %R = {Statistical properties of the Delaunay of random points.} --------------------------------------------------- %N = GS-477 %A = {Nelson, J. M.} %T = {A triangulation algorithm for arbitrary planar domains.} %P = {Appl. Math. Modelling, Vol. 2 (September 1978), 173--183.} %R = {Another version of the divide-and-conquer Voronoi.} --------------------------------------------------- %N = GS-493 %A = {Ohya, T., Iri, M., and Murota, K.} %T = {Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms.} %P = {Journal of the Operations Research Society of Japan Vol. 27 No. 4 (Dec. 1984).} --------------------------------------------------- %N = GS-569 %A = {Seidel, R.} %T = {On the size of closest-point Voronoi diagrams.} %P = {Tech. Rept. F 94, Technische Universit\"at Graz, (Austria, July 1982)} %R = {Gives exact formulas for number of $k$-facets in Voronoi diagrams in $d$-space. Uses correspondence between Voronoi in $d$ dimensions and convex hull in $d+1$ dimensions. Also analyzes the furtherst-point Voronoi.} %K = {convex polyhedra, higher dimensions, Voronoi diagrams, furthest-point Voronoi.} --------------------------------------------------- %N = GS-645 %A = {Toussaint, G. T., and Bhattacharya, B. K.} %T = {On geometric algorithms that use the furthest-point Voronoi diagram.} %P = {Tech. rep. SOCS-81.3, School of Computer Science, McGill Univ. (Canada), Jan. 1981.} %R = {Proves that an edge $e$ of the furthest-point Voronoi diagram is the diameter of a point set $P$ if and only if $P$ is contained in the circle whose diameter is $e$. Therefore, the diameter of $P$ is not necessarily realized by an edge of the f.p.V.d., and many algorithms that use this ``fact'' are trash.} --------------------------------------------------- %N = GS-659 %A = {Voronoi, G.} %T = {Nouvelles applications des parametres continus \`a la th\'eorie des formes quadratiques. Deuxi\`eme m\'emoire: Recherches sur les paralleloedres primitifs.} %P = {J. Reine und Angewandte Math. Vol. 134 (1908) 198--287.} %R = {Historical interest.} --------------------------------------------------- %N = GS-661 %A = {Watson, D. F.} %T = {Computing the $n$-dimensional Delaunay tesselation with application to Voronoi polytopes.} %P = {The Computer Journa Vol. 24 No. 2 (1981), 167--172} %R = {Computes Voronoi diagrams in dimension $d\geq 2$. Works on the Delaunay (represented as a list of cells, each a tuple of sites). Uses an incremental method: to adda new point, locate by brute force all cells whose circumsphere contains the point, and break each into $d+1$ new cells. If the points are inserted in order of $x$-coordinate, then a cell with center $c$ and radius $r$ can be output (and deleted from the list) as soon as $\left| x_{curr}-x_{c}\right| > r$.\par For a random collection of points, the average number of potentially incomplete regions is $O(n^{1-1/k})$, so the total time is $O(n^{2-1/k})$ (hand-wawing). Worst case time is at least $\Omega(n^2)$, probably much more.\par Discusses handling of degeneracies, points at infinity and arithmetic errors (mentions the ``don't ask twice'' technique). Says (erroneously) that the Delaunay neighbors of a site form a convex polytope.} %K = {Voronoi diagram, Delaunay diagram, closest-point problem, higher dimensions, incremental algorithms, degeneracies, average-case analysis.} --------------------------------------------------- %N = GS-785 %A = {Joe, B.} %T = {Delaunay triangular meshes in convex polygons.} %P = {Technical report CS-84-15, CS Department, University of Waterloo (1984).} --------------------------------------------------- %N = GS-81 %A = {Bentley, J. L., Weide, B. W., and Yao, A. C.} %T = {Optimal expected-time algorithms for closest-point problems.} %P = {ACM Transactions on Mathematical Software Vol. 6. No. 4 (December 1980), 563--580. Also Allerton Conf. Proc.? (Date unknown), 843--851. Also Tech. Rep. CMU-CS-79-111, Carnegie-Mellon Univ., Mar. 1979} %R = {Closest-point algorithms using cell techniques (assumes uniform or nearly uniform distribution in some bounded region). In particular: Post-office in $k$-space ($O(n)$ prep. and storage, $O(1)$ query); All-nearest-neighbors in $k$-space ($O(n)$ space and time); Voronoi and MST in the plane ($O(n)$ space and time); MST in $k$-space ($O(n)$ storage, $O(n\log\log n)$ time for $k$ fixed); Voronoi in $k$-space (computes any given region in $O(1)$ time with probability tending to 1).} %K = {nearest neighbor problem, closest-point problem, Voronoi diagram, minimum spanning tree, cell technique, average-case analysis, higher dimensions.} --------------------------------------------------- %N = GS-94 %A = {Bowyer, A.} %T = {Computing Dirichlet tesselations.} %P = {The Computer Journal Vol. 24 No. 2 (1981), 162--166} %R = {Moderately important. Dirichlet (i.e., Voronoi) tesselations in $d$ dimensions. Represents the Voronoi by the unordered adjacency lists. Uses a variant of the incremental algorithm (nicely described). Uses also an iterative point-location algorithm (based on moving closer to the query point along the edges of the Delaunay) that runs on average time $O(n^{1/k})$ for random set of sites; from this concludes $O(n^{1+1/k})$ average time for the whole algorithm (fixed $k$). Worst-case time unknown.} %K = {Voronoi diagram, Delaunay diagram, higher dimensions, incremental algorithm, closest-point algorithm, handling degeneracies, higher dimensions, average-case analysis.} -------------------------------------------------- jorge stolfi