Randomized incremental construction of Delaunay and Voronoi diagrams

A. Aggarwal, H. Imai, N. Katoh, and S. Suri, Findingk points with minimum diameter and related problems,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 283–291.

G. Andrews,The Theory of Partitions, Addison-Wesley, Reading, MA, 1976. (Encyclopedia of Mathematics and Its Applications, Volume 2.)

I. Bárány, J. Schmerl, S. Sidney, and J. Urrutia, A combinatorial result about points and balls in Euclidean space,Discrete Comput. Geom.,3 (1988), 259–262.

J. Bentley, B. Weide, and A. Yao, Optimal expected time algorithms for closest point problems,ACM Trans. Math. Software,6 (1980), 563–580.

J.-D. Boissonnat, and M. Teillaud, A hierarchical representation of objects: the Delaunay tree,Proc. 2nd ACM Symp. on Computational Geometry, 1986, pp. 260–268.

B. Chazelle, H. Edelsbrunner, L. Guibas, R. Seidel, and M. Sharir, Selecting multiply covered points and reducing the size of Delaunay triangulations, Manuscript, 1989.

P. Chew, The simplest Voronoi diagram algorithm takes linear expected time, Manuscript, 1988.

K. Clarkson, Personal communication, 1989.

K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II,Discrete Comput. Geom.,4 (1989), 387–421.

B. Delaunay, Neue Darstellung der geometrischen Krystallographie,Z. Kryst.,84 (1932), 109–149.

B. Delaunay, Sur la sphère vide,Izv. Akad. Nauk SSSR. Otdel. Mat. Estestv. Nauk,7 (1934), 793–800.

R. Dwyer, Higher dimensional Voronoi diagrams in linear expected time,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 326–333.

H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.

H. Edelsbrunner, L. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput.,15 (1986), 317–340.

H. Edelsbrunner, N. Hasan, R. Seidel, and X. Shen, Circles through two points that always enclose many points, Technical Report UIUCDCS-R-88-1400, University of Illinois at Urbana, January 1988.

S. Fortune, A sweepline algorithm for Voronoi diagrams,Algorithmica,2 (1987), 153–174.

S. Fortune, A note on Delaunay diagonal flips, Unpublished manuscript.

P. Green and R. Sibson, Computing Dirichlet tesselation in the plane,Comput. J.,21 (1977), 168–173.

L. Guibas and M. Sharir, History helps queries, In preparation.

L. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics,4 (1985), 74–123.

J. Jaromczyk and G. Swiatek, Degenerate cases do not require more memory, Manuscript, 1989.

D. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.,12 (1983), 28–35.

D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.

K. Mehlhorn, S. Meiser, and C. Ó'Dúnlaing, On the construction of abstract Voronoi diagrams, Manuscript, 1989.

K. Mulmuley, A fast planar partition algorithm, Technical Report 88-107, Department of Computer Science, University of Chicago, May 1988.

F. Preparata and M. Shamos,Computational Geometry-An Introduction, Springer-Verlag, Berlin, 1985.

F. Preparata and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 558–567.

R. Seidel, Private communication.

G. Voronoi, Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier Mémoire: Sur quelques proprieteés des formes quadratiques positives parfaites,J. Reine Angew. Math.,133 (1907), 97–178.

G. Voronoi, Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième Mémoire: Recherches sur les parallélloèdres primitifs,J. Reine Angew. Math.,134 (1908), 198–287;136 (1909), 67–181.