Voronoi diagrams—a survey of a fundamental geometric data structure

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98567]
	2	A. Aggarwal , S. Suri, Fast algorithms for computing the largest empty rectangle, Proceedings of the third annual symposium on Computational geometry, p.278-290, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41988]
	3	A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100260]
	4	A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
	5	A. Aggarwal , H. Imai , N. Katoh , S. Suri, Fining k points with minimum spanning trees and related problems, Proceedings of the fifth annual symposium on Computational geometry, p.283-291, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73865]
	6	AGGARWAL, A., CHAZELLE, B., GUIBAS, L. J., O'DUNLAING, C., AND YAP, C. K. 1988. Parallel computational geometry. Algorithmica 3, 293-327.
	7	AHUJA, N. 10~2. Dot pattorn processing using Voronoi polygons as neighborhoods. IEEE Trans. Patt. Anal. Mach. Int. PAMI-4, 336-343.
	8	AKL, S. 1983 A note on Euclidean matchings, triangulations, and spanning trees. J. Comb. Inf. Syst. Sci. 8, 169-174.
	9	ALEXANDERSON, G. L., AND WETZEL, J. E. 1978. Simple partition of space. Math. Magazine 51, 220-225.
	10	ALT, H., AND YAP, C. K. 1990. Algorithmic aspects of motion planning: A tutorial (part 2). Algorithms Rev. 1, 61-77.
	11	Hiromi Aonuma , Hiroshi Imai , Keiko Imai , Takeshi Tokuyama, Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams, Proceedings of the sixth annual symposium on Computational geometry, p.225-234, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98575]
	12	ARNOLD, D. B., AND MILNE, W. J. 1984. The use of Voronoi tessellations in processing soil survey results. IEEE Comput. Graph. Appl. 4, 22-30.
	13	ARONOV, B. 1989. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4, 109-140.
	14	B. Aronov , S. Fortune , G. Wilfong, The furthest-site geodesic Voronoi diagram, Proceedings of the fourth annual symposium on Computational geometry, p.229-240, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73417]
	15	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Proceedings of the sixth annual symposium on Computational geometry, p.112-115, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98548]
	16	ASANO, T., AND ASANO, T. 1986. Voronoi diagram for points in a simple polygon. In Perspectives in Computing 15, D. S. Johnson, T. Nishizeki, A. Nozaki, H. S. Will Eds. Academic Press, New York, pp. 51-64.
	17	T. Asano , B. Bhattacharya , M. Keil , F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.252-257, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73419]
	18	ASH, P. F., AND BOLKER, E. D. 1985. Recognizing Dirichlet tessellations. Geometriae Dedicata 19, 175-206.
	19	ASH, P. F., AND BOLKER, E. D. 1986. Generalized Dirichlet tessellations. Geometrme Dedicata 20, 209-243.
	20	ASH, P. F., BOLKER, E. D., CRAPO, H., AND WHITE- LEY, W. 1988. Convex polyhedra, Dirichlet tessellations, and spider webs. In Shaping Space: A Polyhedral Approach, M. Senechal and G. Fleck, Ed~. Birkh/iuser, Boston, pp. 231-250.
	21	AUGENBAUM, J. M., AND PESKIN, C. S. 1985. On the construction of the Voronoi mesh on a sphere. J. Comput. Phys. 59, 177-192.
	22	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	23	AURENHAMMER, F. 1987b. A criterion for the affine equivalence of cell complexes in R d and convex polyhedra in Rd+ 1. Discrete Comput. Geometry 2, 49-64.
	24	F. Aurenhammer, Recognising polytopical cell complexes and construcing projection polyhedra, Journal of Symbolic Computation, v.3 n.3, p.249-255, June 1987 [doi>10.1016/S0747-7171(87)80003-2]
	25	F. Aurenhammer, Improved algorithms for disc and balls using power diagrams, Journal of Algorithms, v.9 n.2, p.151-161, June 1988 [doi>10.1016/0196-6774(88)90035-1]
	26	AURENHAMMER, F. 1988b. Linear combinations from power domains. Geometriae Dedicata 28, 45-52.
	27	Franz Aurenhammer, A new duality result concerning Voronoi diagrams, Discrete & Computational Geometry, v.5 n.3, p.243-254, May 1990 [doi>10.1007/BF02187788]
	28	F. Aurenhammer, A relationship between Gale transforms and Voronoi diagrams, Discrete Applied Mathematics, v.28 n.2, p.83-91, Aug. 1990 [doi>10.1016/0166-218X(90)90108-O]
	29	AURENHAMMER, F., AND EDELSBRUNNER, $. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition 17, 251-257.
	30	AURENHAMMER, F., AND IMAI, H. 1988. Geometric relations among Voronoi diagrams. Geometriae Dedicata 27, 65-75.
	31	Franz Aurenhammer , Otfried Schwarzkopf, A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.142-151, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109664]
	32	AURENHAMMER, F., AND STOCKL, G. 1988. On the peeper's Voronoi diagram. Rep. 264, IIG-TU Graz, Austria.
	33	AURENHAMMER, F., ST(SCKL, G., AND WELZL, E. 1991. The post-office problem for fuzzy point sets. Rep. 91-07, FU Berlin, Germany.
	34	AVIS, D., AND BHATTACHARYA, B. K. 1983. Algorithms for computing d-dimenslonal Voronoi diagrams and their duals. Adv. Comput. Res. 1,159-180.
	35	BABENKO, V. F. 1977. On the optimal cubature ormulae on certain classes of continuous functions. Analys~s Math. 3, 3-9.
	36	BADDELEY, A. 1977. A fourth note on recent research in geometrical probability. Adv. Appl. Probab. 9, 824-860.
	37	Avikam Balstan , Micha Sharir, On the shortest paths between two convex polyhedra, Journal of the ACM (JACM), v.35 n.2, p.267-287, April 1988 [doi>10.1145/42282.214094]
	38	BENTLEY, J. L., AND MAURER, H. A. 1979. A note on Euclidean near neighboring searching in the plane. Inf. Process. Lett. 8, 133-136.
	39	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	40	BERN, M. W., EPPSTEIN, D., AND GILBERT, J. 1990. Provably good mesh generation. Manuscript, XEROX Palo Alto Research Center, Palo Alto, Calif.
	41	BESAG, J. 1974. Spatial interaction and the statistical analysis of lattice systems. J. Roy. Statist. Soc. B 36, 192-236.
	42	BIEBERBACH, L. 1912. 'l)ber die Bewegungsgruppen der euklidischen Riiume I, II. Math. Ann. 72, 400-412.
	43	BLUM, H. 1967. A transformation for extracting new descriptors of shape. In Proceedings of the Symposium on Models for the Perception of Speech and Visual Form. Weiant Whaten- Dunn, Ed. MIT Press, Cambridge, Mass., pp. 362-380.
	44	BLUM, H. 1973. Biological shape and visual science (Part I). J. Theol'. Biol. 38, 205-287.
	45	Jean-Daniel Boissonnat, Shape reconstruction from planar cross sections, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.1-29, Oct. 1988 [doi>10.1016/S0734-189X(88)80028-8]
	46	J D Boissonnat , M Teillaud, The hierarchical representation of objects: the Delaunay tree, Proceedings of the second annual symposium on Computational geometry, p.260-268, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10543]
	47	BOOTS, B. N. 1979. Weighting Thiessen polygons. Econ. Geography, 248-259.
	48	BooTs, B. N. 1986. Voronoi (Thiessen) polygons. In CATMOG 45, Geo Books, Norwich, Conn.
	49	BOWYER, A. 1981. Computing Dirichlet tessellations. Computer J. 24, 162-166.
	50	BRASSEL, K. E., AND REIF, D. 1979. A procedure to generate Thiessen polygons. Geograph. Anal. 11,289-303.
	51	E. Brisson, Representing geometric structures in d dimensions: topology and order, Proceedings of the fifth annual symposium on Computational geometry, p.218-227, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73858]
	52	BRONDSTED, A. 1983. An Introduction to Convex Polytopes. Springer, New York, Heidelberg, Berlin.
	53	BRosTow, W., AND SICOTTE, Y. 1975. Coordination number in liquid argon. Physica A 80, 513-522.
	54	BROSTOW, W., DUSSAULT, J. P., AND FOX, B. L. 1978. Construction of Voronoi polyhedra. J. Comput. Phys. 29, 81-92.
	55	BROWN, K. Q. 1979. Voronoi diagrams from convex hulls. Inf. Process. Lett. 9,223-228.
	56	Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
	57	BRUMBERGER, H. AND GOODISMAN. 1983. Voronoi cells: An interesting and potentially useful cell model for interpreting the small angle scattering of catalysts. J. Appl. Crystallogr. 16, 83-88.
	58	CALABI, L., AND HARTNETT, W.E. 1968. Shape recognition, prairie fires, convex deficiencies, and skeletons. Am. Math. Monthly 75, 335-342.
	59	John Canny , Bruce Donald, Simplified Voronoi diagrams, Discrete & Computational Geometry, v.3 n.3, p.219-236, Jan., 1988 [doi>10.1007/BF02187909]
	60	Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
	61	B. Chazelle , H. Edelsbrunner, An improved algorithm for constructing kth-order voronoi diagrams, IEEE Transactions on Computers, v.36 n.11, p.1349-1354, Nov. 1987 [doi>10.1109/TC.1987.5009474]
	62	B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
	63	B Chazelle , R L Drysdale , D T Lee, Computing the largest empty rectangle, SIAM Journal on Computing, v.15 n.1, p.300-315, Feb. 1986 [doi>10.1137/0215022]
	64	B Chazelle , R Cole , P Preparata , C Yap, New upper bounds for neighbor searching, Information and Control, v.68 n.1-3, p.105-124, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80030-4]
	65	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , John E. Hershberger , Raimund Seidel , Micha Sharir, Slimming down by adding; selecting heavily covered points, Proceedings of the sixth annual symposium on Computational geometry, p.116-127, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98551]
	66	CHrR~TON, D., AND TARJAN, R. E. 1976. Finding minimum spanning trees. SIAM J. Comput. 5, 724-742.
	67	P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
	68	CHEW, L. P. 1989a. Constrained Delaunay triangulations. Algorithmica 4, 97-108.
	69	HEW, L. P. 1989b. Guaranteed-quality triangular meshes. Rep. TR 89-983, Dept. Comput. Sci., Cornell Univ., Ithaca, N.Y.
	70	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
	71	L. P. Chew , K. Kedem, Placing the largest similar copy of a convex polygon among polygonal obstacles, Proceedings of the fifth annual symposium on Computational geometry, p.167-173, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73853]
	72	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	73	CI~ISTOFIDES, N. 1976. Worst-case analysis of a new heuristic for the traveling salesman problem. Symposium on Algorithms and Complexity, Carnegie-Mellon Univ., Penn.
	74	CLARKSON, K. L. 1987. New applications of random sampling to computational geometry. Discrete Comput. Geom. 2, 195-222.
	75	CLARKSON, K. L. 1989. An algorithm for geometric minimum spanning trees requiring nearly linear expected time. Algorithmica4, 461-468.
	76	K. L. Clarkson , P. W. Shor, Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, Proceedings of the fourth annual symposium on Computational geometry, p.12-17, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73395]
	77	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	78	Richard Cole , Michael T. Goodrich , Colm Ó Dúnlaing, Merging free trees in parallel for efficient Voronoi diagram construction, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.432-445, July 1990, Warwick University, England
	79	CONWAY, J. M., AND SLOAN~, N. J. A. 1982. Voronoi regions of lattices, second moments of polytopes, and quantization. IEEE Trans. Inf. Theory IT-28, 211-226.
	80	CRAIg, L. K. 1978. The Monte Carlo generation of random polygons. Comput. Geosci. 4, 131-141.
	81	CRAPO, H. 1979. Structural rigidity. Struct. Topol. 1, 13-45.
	82	CRuz ORIVE, L.-M. 1979. Distortion of certain Voronoi tessellations when one particle moves. J. Appl. Probab. 16, 95-103.
	83	DAVID, E. E., A~D DAVID, C. W. 1982. Voronoi polyhedra as a tool for studying solvation structure. J. Chem. Phys. 76, 4611-4614.
	84	DE FLORIANI, L., FALCIDIENO, B., PIENOVI, C., AND NAG~, G. 1988. On sorting triangles in a Delaunay tessellation. Rep. Inst. Mat. Appl., Consiglio Nazionale della Richerche, Genova, Italy.
	85	DEHNE, F., AND KLEIN, R. 1987. An optimal algorithm for computing the Voronoi diagram on a cone. Rep. SCS-TR-122, School Comput. Sci., Carleton Univ., Ottawa, Canada.
	86	F. Dehne , H. Noltemeier, A computational geometry approach to clustering problems, Proceedings of the first annual symposium on Computational geometry, p.245-250, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323265]
	87	DELAUNAY, B. N. 1932. Neue Darstellung der geometrischen Kristallographie. Z. Kristallograph. 84,109-149.
	88	DELAUNAY, B. N. 1934. Sur la sphere vide. Bull. Acad. Science USSR VII: Class. Sci. Math., 793-800.
	89	DELAUNAY, B. N. 1963. Theorie der regul~iren Dirichletschen Zerlegungen des n-dimensionalen euklidischen Raumes. Schrifienre~he Int. Math. Dtsch. Akad. Wiss. Berlin 13, 27-31.
	90	DELAUNAY, B. N., DOLBILIN, N. P., AND STOGRIN, M. I. 1978. Combinatorial and metric theory of planigons. Trudy Mat. Inst. Steklov 148, 109-140.
	91	DEWDNEY, A. K. 1977. Complexity of nearest neighbour searching in three and higher dimensions. Rep. 28, Univ. of Western Ontario, London, Ontario.
	92	DEWDNEY, A. K., AND VRANCH, J. K. 1977. A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem. Util. Math. 12, 193-199.
	93	Michael B. Dillencourt, Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations, Information Processing Letters, v.24 n.5, p.339-342, 16 March 1987 [doi>10.1016/0020-0190(87)90160-8]
	94	Michael B. Dillencourt, A non-Hamiltonian, nondegenerate Delaunay Triangulation, Information Processing Letters, v.25 n.3, p.149-151, May 29, 1987 [doi>10.1016/0020-0190(87)90124-4]
	95	M. Dillencourt, Toughness and Delaunay triangulations, Proceedings of the third annual symposium on Computational geometry, p.186-194, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41978]
	96	DIRICHLET, G. L. 1850. Uber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. J. Re~ne u. Angew. Math. 40, 209-227.
	97	DOBKIN, D. P., AND LASZLO, M. J. 1989. PrimL tives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 3-32.
	98	DOBKIN, D. P., AND LmTON, R. J. 1976. Multidimensional searching problems. SIAM J. Comput. 5, 181-186.
	99	David P. Dobkin , Steven J. Friedman , Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs, Discrete & Computational Geometry, v.5 n.4, p.399-407, Jul. 1990 [doi>10.1007/BF02187801]
	100	Robert L. (Scot) Drysdale, III, A practical algorithm for computing the Delaunay triangulation for convex distance functions, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.159-168, January 22-24, 1990, San Francisco, California, United States
	101	DWYER, R. A. 1987. A faster divide-and-conquer algorithm for constructing Delaunay triangulations. Algorithmica 2, 137-151.
	102	R. A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Proceedings of the fifth annual symposium on Computational geometry, p.326-333, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73869]
	103	Ta. Asano, A new point-location algorithm and its practical efficiency: comparison with existing algorithms, ACM Transactions on Graphics (TOG), v.3 n.2, p.86-109, April 1984 [doi>10.1145/357337.357338]
	104	H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
	105	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	106	H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Proceedings of the fifth annual symposium on Computational geometry, p.145-151, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73850]
	107	EDELSBRUNNER, H., AND MAURER, H. A. 1985. Finding extreme points in three dimensions and solving the post-office problem in the plane. Inf. Process. Lett. 21, 39-47.
	108	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	109	EDELSBRUNNER, H., AND WELZL, E. 1985. On the number of line separations of a finite set in the plane. J. Combin. Theory Ser. A, 15-29.
	110	EDELSBRUNNER, H., GUIBAS, L. J., AND S~A~m, M. 1989. The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4, 311-336.
	111	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	112	EDELSBRUNNER, H., KIRKPATRICK, D. G., AND SEIDEL, R. 1983. On the shape of a set of points in the plane. IEEE Trans. Inf. Theory IT-29,551-559.
	113	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	114	H. Edelsbrunner , G. Rote , E. Welzl, Testing the necklace condition for shortest tours and optimal factors in the plane, 14th International Colloquium on Automata, languages and programming, p.364-375, July 1987, Karlsruhe, Germany
	115	EHRLICH, P. E., AND IM HOF, H. C. 1979. Dirichlet regions in manifolds without conjugate points. Comment. Math. Helvet. 54,642-658.
	116	EISELT, H. A., AND PEDERZOLI, G. 1986. Voronoi diagrams and their use: A survey. Part I: Theory; Part II: Applications. In S. Goyal, Ed. Proceedings of the ASAC 7, 2. pp. 98-115.
	117	ENGEL, P. 1981. 'lJber Wirkungsbereichsteilungen mit kubischer Symmetrie. Z. Kristallograph. 154, 199-215.
	118	D. Eppstein, Finding the k smallest spanning trees, Proceedings of the second Scandinavian workshop on Algorithm theory, p.38-47, July 1990, Bergen, Sweden
	119	FAIRFIELD, J. 1979. Contoured shape generation: Forms that people see in dot patterns. In Proceedings of the IEEE Conference on Systems Man Cybernetics. pp. 60-64.
	120	FAIRFIELD, J. 1983. Segmenting dot patterns by Voronoi diagram concavity. IEEE Trans. Part. Anal. Mach. Int. PAMI-5, 104-110.
	121	FEDEROFF, E. S. 1885. Elemente der Lehre yon den Figuren. Verh. Russ Min. Ges. St. Petersburg 21, 1-279.
	122	D A Field, Implementing Watson's algorithm in three dimensions, Proceedings of the second annual symposium on Computational geometry, p.246-259, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10542]
	123	FINNEY, J. L. 1979. Procedure for the construction of Voronoi polyhedra. Note. J. Comput. Phys. 32, 137-143.
	124	Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
	125	FORTUNE, S. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153-174.
	126	FORTUNE, S. 1988. Sorting helps for Voronoi diagrams. Manuscript, ATT Bell Lab., Murray Hill, N.J.
	127	FRANK, F. C., AND KASPER, J. S. 1958. Complex alloy structures regarded as sphere packings. Acta Crystallogr. 11,184-190.
	128	GABRIEL, K. R, AND SOKAL, R. R. 1969. A new statistical approach to geographic variation analysis. Syst. Zoology 18, 259-278.
	129	GAMBINI, R. 1966. A computer program for calculating lines of equilibrium between multiple centers of attraction. Manuscript, Center of Regional Studies, Univ. of Kansas, Lawrence, Kan.
	130	M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
	131	GAUSS, C. F. 1840. Recursion der 'Untersuchungen fiber die Eigenschaften der positiven tern~iren quadratischen Formen von Ludwig August Seeber. J. Reine Angew. Math. 20, 312-320.
	132	GILBERT, E. N. 1962. Random subdivisions of space into crystals. Ann. Math. Star. 33, 958-972.
	133	Michael T. Goodrich , Colm Ó'Dúnlaing , Chee-Keng Yap, Constructing the Voronoi Diagram of a Set of Line Segments in Parallel (Preliminary Version), Proceedings of the Workshop on Algorithms and Data Structures, p.12-23, August 17-19, 1989
	134	GOWDA, I. G., KIRKPATRICK, D. G., LEE, D. T., AND NAAMAD, A. 1983. Dynamic Voronoi diagrams. IEEE Trans. Inf Theory IT-29, 724-731.
	135	GREEN, P. J., AND SIBSON, R. 1977. Computing Dirichlet tesselations in the plane. Comput. J. 21, 168-173.
	136	GRUBER, P. M., AND LEKKERKERKER, C. G. 1988. Geometry of Numbers. North-Holland Publishing Co., Amsterdam.
	137	GRUBER, P. M., AND RYSKOV, S. S. 1987. Facet-tofacet implies face-tofface. Manuscript.
	138	GRfiNBAUM, B. 1967. Convex Polytopes. Interscience, New York.
	139	GRfJNBAUM, B., AND SHErHARD, G. C. 1980. Tilings with congruent tiles. Bull. Am. Math. Soc. 3, 951-973.
	140	Branko Grünbaum , G C Shephard, Tilings and patterns, W. H. Freeman & Co., New York, NY, 1986
	141	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	142	Leonidas J. Guibas , Donald E. Knuth , Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.414-431, July 1990, Warwick University, England
	143	GUIBAS, L. J., MITCHELL, J. S. B., AND ROOS, T. 1991. Voronoi diagrams of moving points in the plane. Springer LNCS. In press.
	144	John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
	145	H. Heusinger , H. Noltemeier, On separable clusterings, Journal of Algorithms, v.10 n.2, p.212-227, June 1989 [doi>10.1016/0196-6774(89)90013-8]
	146	Klaus Hinrichs , Jug Nievergelt , Peter Schorn, Plane-sweep solves the closest pair problem elegantly, Information Processing Letters, v.26 n.5, p.255-261, Jan. 11, 1988 [doi>10.1016/0020-0190(88)90150-0]
	147	K. Hinrichs , J. Nievergelt , P. Schorn, A sweep algorithm for the all-nearest-neighbors problem, Proceedings on International Workshop on Computational Geometry on Computational Geometry and its Applications, p.43-54, October 1988, Wu:9Airzburg, Germany
	148	HORTON, R. E. 1917. Rational study of rainfall data make~ possible bettor estimates of water yield. Eng. News-Record, 211-213.
	149	HOWE, S. E. 1978. Estimating regions and clustering spatial data: Analysis and implementation of methods using the Voronoi diagram. Ph.D. dissertation, Brown Univ., Providence, R.I.
	150	Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
	151	F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
	152	IMAI, H., IRI, M., AND MUROTO, K. 1985. Voronoi diagram in the Laguerre geometry and its applications. SIAM J. Comput. 14, 93-105.
	153	K. Imai , S. Sumino , H. Imai, Minimax geometric fitting of two corresponding sets of points, Proceedings of the fifth annual symposium on Computational geometry, p.206-275, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73863]
	154	JOHNSON, W. A., AND MEHL, R. F. 1939. Reaction kinetics in processes of nucleation and growth. Trans. Am. Instit. Mining Metall. A.LM.M.E. 135, 416-458.
	155	KANTABUTRA, V. 1983. Traveling salesman cycles are not always subgraphs of Voronoi duals. Inf. Process. Lett. 16, 11-12.
	156	J. Mark Keil , Carl A. Gutwin, The Delauney Triangulation Closely Approximates the Complete Euclidean Graph, Proceedings of the Workshop on Algorithms and Data Structures, p.47-56, August 17-19, 1989
	157	KL~NG, T. 1966. Random fragmentation in two and three dimensions. Z. Astrophysik 64, 433-439.
	158	KmKPATRICK, D. G. 1979. Efficient computation of continuous skeletons. In Proceedings of the 20th Annual IEEE Symposium on FOCS. pp. 18-27.
	159	KmKPATRICK, D. G. 1980. A note on Delaunay and optimal triangulations. Inf Process. Lett. 10, 127-128.
	160	KmKPATRICK, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 28-35.
	161	KLEE, V. 1980. On the complexity of d-dimensional Voronoi diagrams. Archiv Math. 34, 75-80.
	162	KLEIN, R. 1989. Concrete and Abstract Voronoi D~agrams. Springer LNCS 400.
	163	Rolf Klein , Derick Wood, Voronoi Diagrams Based on General Metrics in the Plane, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.281-291, February 11-13, 1988
	164	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	165	KocH, E. 1973. Wirkungsbereichspolyeder und Wirkungsbereichsteilungen zu kubischen Gitterkomplexen mit weniger als drei Freiheitsgraden. Z. Kristallograph. 138, 196-215.
	166	KOrEC, R. J. 1963. An alternative method for the construction of Thiessen polygons. Professional Geographer 15, 24-26.
	167	KUUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Problem. Am. Math. Soc. 7, 48-50.
	168	LANTUEJOUL, C., AND MAISONNEUVE, F. 1984. Geodesic methods in quantitative image analysis. Pattern Recogn. 17, 177-187.
	169	LAVES, P. 1930. Ebeneneinteilung in Wirkungsbereiche. Z. Kristallograph. 76, 277-284.
	170	LAWSON, C. L. 1972. Generation of a triangular grid with applications to contour plotting. Tech. Memorandum 299, California Inst. Tech. Jet Propulsion Lab.
	171	LAWSON, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. Rice Ed., Academic Press, New York.
	172	D. T. Lee, Two-Dimensional Voronoi Diagrams in the Lp-Metric, Journal of the ACM (JACM), v.27 n.4, p.604-618, Oct. 1980 [doi>10.1145/322217.322219]
	173	LEE, D. T. 1982a. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. C-31,478-487.
	174	LEE, D. T. 1982b. Medial axis transform of a planar shape. IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4, 363-369.
	175	LEE, D. T., AND DRYSDALE, R. L. 1981. Generalization of Voronoi diagrams in the plane. SIAM J. Comput. 10, 73-87.
	176	LEE, D. T., AND LIN, A. K. 1986. Generalized Delaunay triangulation for planar graphs. Discrete Comput. Geom. 1,201-217.
	177	LEE, D. T., AND PREPARATA, F. P. 1984. Computational geometry--A survey. IEEE Trans. Cornput. C.33, 12, 1072-1101.
	178	LEE, D. T., AND SCHACHTER, B. J. 1980. Two algorithms for constructing a Delaunay triangulation. Int. J. Comput. Inf. Sci. 9,219-242.
	179	LEE, D. T., AND WONG, C. K. 1980. Voronoi diagrams in the Ll(L~) metrics with 2- dimensional storage applications. SIAM J. Comput. 9,200-211.
	180	LEE, D. T., AND YANG, C. C. 1979. Location of multiple points in a planar subdivision. Inf. Process. Lett. 9, 190-193.
	181	LEVEN, D., AND SnARra, M. 1986. Intersection and proximity problems and Voronoi diagrams. Adv. Robotics 1, 187-228.
	182	LEwd, D., AND SHAem, M. 1987. Planning a purely translational motion of a convex robot in two-dimensional space using Voronoi diagrams. Discrete Comput. Geom. 2, 9 31.
	183	A Lingus, The Greedy and Delaunay triangulations are not bad in the average case, Information Processing Letters, v.22 n.1, p.25-31, January 2, 1986 [doi>10.1016/0020-0190(86)90038-4]
	184	LINGAS, A. 1986b. A fast algorithm for the generalized Delauuay triangulation. Manuscript, Univ. of LinkSping, Sweden.
	185	Andrzej Lingas, Voronoi diagrams with barriers and the shortest diagonal problem, Information Processing Letters, v.32 n.4, p.191-198, Sept 1, 1989 [doi>10.1016/0020-0190(89)90043-4]
	186	LINHART, J. 1981. Die Beleuchtung yon Kugeln. Geom. Dedicata 10, 145-154.
	187	LITTLE, D. V. 1974. A third note on recent research in geometric probability. Adv. Appl. Probab. 6, 103-130.
	188	LOEB, A. L. 1970. A systematic survey of cubic crystal structures. J. Solid State Chem. I, 237-267.
	189	MANACHER, G. K., AND ZOBRIST, A. L. 1979. Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inf. Process. Lett. 9, 31-34.
	190	MATULA, D. W., AND SOKAL, R. R. 1980. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geograph. Anal. 12, 205-221.
	191	MATZKE, E. B., AND NESTLER, J. 1946. Volumeshape relationships in variant foams. Am. J. Botanics 33, 130-144.
	192	MAUS, A. 1884. Delaunay triangulation and the convex hull of n points in expected linear time. BIT 24, 151-163.
	193	MAXWELL, J. C. 1864. On reciprocal diagrams and diagrams of forces. Phil. Mag. 4, 27, 250-261.
	194	McLAIN, D. H. 1976. Two dimensional interpolation from random data. Comput. J. 19, 178-181.
	195	MEGIDDO, N. 1983. Linear time algorithms for linear programming in R3 and related problems. SlAM J. Comput. 12, 759-776.
	196	K. Mehlhorn , S. Meimer , C. ÓDùnlaing, On the construction of abstract Voronoi diagrams, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.227-239, February 1990, Rouen, France
	197	MEIJERING, J. L. 1953. Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Res. Rept. 8, 270-290.
	198	MILES, R. E. 1970. On the homogenous planar Poisson process. Math. Biosci. 6. 85-127.
	199	Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
	200	MOLLISON, D. 1977. Spatial contact models for ecological and epidemic spread. J. Roy. Stat. Soc. B 39,283-326.
	201	U. Montanari, A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance, Journal of the ACM (JACM), v.15 n.4, p.600-624, Oct. 1968 [doi>10.1145/321479.321486]
	202	MORAN, P. A. P. 1966. A note on recent research in geometric probability. J. Appl. Probab. 3, 53-463.
	203	MORAN, P. A. P. 1969. A second note on recent research in geometrical probability. Adv. Appl. Probab. 1, 73-89.
	204	MOUNT, D. M. 1985. Voronoi diagrams on the surface of a polyhedron. Rep. 1496, Univ. of Maryland.
	205	D Mount, Storing the subdivision of a polyhedral surface, Proceedings of the second annual symposium on Computational geometry, p.150-158, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10532]
	206	D. M. Mount , A. Saalfeld, Globally-Equiangular triangulations of co-circular points in 0(n log n) time, Proceedings of the fourth annual symposium on Computational geometry, p.143-152, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73408]
	207	MUDER, D. J. 1988a. How big is an n-sided Voronoi polygon? Manuscript, MITRE Corp., Bedford, Mass.
	208	MUDER, D. J. 1988b. Putting the best face on a Voronoi polyhedron. Proc. London Math. Soc. 56, 329-348.
	209	Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
	210	MURTADH, F. 1983. A survey of recent advances in hierarchical clustering algorithms. Computer J. 26, 354-359.
	211	NEWMAN, C. M., RINOTT, Y., AND TVE~SKY, A. 1983. Nearest neighbor and Voronoi regions in certain point processes. Adv. Appl. Probab. 15, 726-751.
	212	NIGGLI, R. 1927. Die topologische Strukturanalyse. Z. KristaUograph. 65, 391-415.
	213	NOWACKI, W. 1933. Der Begriff 'Voronoischer Bereich'. Z. Kristallograph. 85, 331-332.
	214	NOWACKI, W. 1976. Uber allgemeine Eigenschaften von Wirkungsbereichen. Z. KristaUograph. 143, 360-368.
	215	O'DUNLAING, C., AND YAP, C. K. 1985. A "retraction'' method for planning the motion of a disc. J. Algorithms 6, 104-111.
	216	O'DUNLAING, C., SHARIR, M., AND YAP, C. K. 1986. Generalized Voronoi diagrams for moving a ladder: I. Topological analysis. Comm. Pure Appl. Math. 39,423-483.
	217	O'DUNLAING, C., SHARm, M., AND YAP, C. K. 1987. Generalized Voronoi diagrams for moving a ladder: II. Efficient construction of the diagram. Algorithmica 2, 27-59.
	218	Takao Ohya , Masao Iri , Kazuo Murota, A fast voronoi-diagram algorithm with quaternary tree bucketing, Information Processing Letters, v.18 n.4, p.227-231, May 1984 [doi>10.1016/0020-0190(84)90116-9]
	219	OHYA, T., IRI, M., AND MUROTA, K. 1984b. Improvements of the incremental methods for the Voronoi diagram with computational comparison of various algorithms. J. Operations Res. Soc. Japan 27, 306-337.
	220	OKABE, A., YOSHIKAWA, T., FUJII, A., AND OIKAWA, K. 1988. The statistical analysis of a distribution of active points in relation to surface-like elements. Environ. Plan. A 20, 609-620.
	221	OVERMARS, M. 1981. Dynamization of order decomposable set problems. J. Algorithms 2, 245-260.
	222	PACH, J., AND SHARIR, M. 1989. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates. Discrete Comput. Geom. 4,291-310.
	223	PAPADTMITRIOU, C. H. 1977. The Euclidean traveling salesman problem is NP-complete. Theor. Comp. Sci. 4,237-244.
	224	PASCHINGER, I. 1982. Konvexe Polytope und Dirichletsche Zellenkomplexe. Ph.D. Dissertation, Inst. f, Math., Univ. Salzburg, Austria.
	225	PmLBRICK, 0. 1968. Shape recognition with the medial axis transform. In P~ctorial Pattern Reeognitwn, G. C. Cheng, R. S. Ledley, D. K Pollock, and A. Rosenfeld, Eds. Washington, D.C.
	226	PRErARATA, F. P. 1977. Steps into computational geometry. Rep. R-760, Coordinated Science Lab., Univ. of Illinois, Urbana, Ill., pp, 23-24.
	227	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	228	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	229	PRIM, R. C. 1957. Shortest connection networks and some generalizations Bell Syst. Tech. J. 36, 1389-1401.
	230	V. T. Rajan, Optimality of the Delaunay triangulation in R^d, Proceedings of the seventh annual symposium on Computational geometry, p.357-363, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109688]
	231	RHYNSBURGER, D. 1973. Analytical delineation of Thiessen polygons. Geograph. Anal. 5, 133-144.
	232	S. Rippa, Minimal roughness property of the Delaunay triangulation, Computer Aided Geometric Design, v.7 n.6, p.489-497, Nov. 1990 [doi>10.1016/0167-8396(90)90011-F]
	233	ROGERS, C. A. 1964. Packing and Covering. Cambridge University Press, London, New York.
	234	Hans Rohnert, Moving Discs Between Polygons, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.502-515, July 11-15, 1988
	235	ROSENBERCER, H. 1988. Order-k Voronoi diagrams of sites with additive weights in the plane. Rep. UIUCDCS-R-88-1431, Dept. Cornput. Sci., Univ. Illinois, Urbana, Ill.
	236	ROSENKRANTZ, D. J., STEARNS, R. E., AND LEWm, P. M. 1977. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563-581.
	237	Peter Forbes Rowat, Representing spatial experience and solving spatial problems in a simulated robot environment, 1979
	238	SAI<AMOTO, M., AND TAKAGI, M. 1988. Patterns of weighted Voronoi tessellations. Sct. Form 3, 103-111.
	239	SCH()NFLIES, A. 1891. Kristallsysteme und Kirstallstruktur. Teubner, Leipzig.
	240	SCHWARTZ, J., AND YAP, C. K. 1986. Advances in Robotics. Lawrence Erlbaum Associates, Hillside, N.J.
	241	O. Schwarzkopf, Parallel computation of discrete Voronoi diagrams, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, p.193-204, February 1989, Paderborn, Germany
	242	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	243	SEIDEL, R. 1982 The complexity of Voronoi diagrams in higher dimensions. In Proceedings of the 20th Annual Allerton Conference on CCC. pp. 94-95.
	244	SEIDEL, R. 1985 A method for proving lower bounds for certain geometric problems. In Computational Geometry, G. T. Toussaint Ed. pp. 319-334.
	245	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	246	R. Seidel, On the number of faces in higher-dimensional Voronoi diagrams, Proceedings of the third annual symposium on Computational geometry, p.181-185, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41977]
	247	SEIDEL, R. 1988. Constrained Delaunay triangulations and Voronoi diagrams with obstacles. In Rep. 260, IIG-TU Graz, Austria, pp. 178-191.
	248	Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
	249	Michael Ian Shamos, Computational geometry., 1978
	250	SR^MOS, M. I., AND HOEY, D. 1975. Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on FOCS pp. 151-162.
	251	SHARm, M. 1985. Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14,448-468.
	252	SmsoN, R. 1977. Locally equiangular triangulations. Comput. J. 21,243-245.
	253	SmsoN, R. 1979. The Dirichlet tessellation as an aid in data analysis. Scandinavian J. Stat. 7, 14-20.
	254	SmsoN, R. 1980. A vector identity for the Dlrichlet tessellation. Math. Proc. Camb. Phil. Soc. 87, 151-155.
	255	S Sifrony , M Sharir, A new efficient motion-planning algorithm for a rod in polygonal space, Proceedings of the second annual symposium on Computational geometry, p.178-186, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10535]
	256	SMITH, C. S. 1954. The shape of things. Sci. Am. 58-64.
	257	SNYDEe, D. E. 1962. Urban places in Uruguay and the concept of a hierarchy. Festschrift: C. F. Jones. Northwestern University Studies in Geography 6, 29-46.
	258	STIFTER, S. 1989. An axiomatic approach to Voronoi diagrams in 3D. Manuscript, RISC, Univ. of Linz, Austria.
	259	SUGISARA, K., AND IRI, M. 1988. Geometric algorithms in finite-precision arithmetic. Research Memorandum RMI 88-10, Faculty of Engineering, Univ. of Tokyo, Japan.
	260	Kenneth J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the ACM (JACM), v.30 n.3, p.428-448, July 1983 [doi>10.1145/2402.322386]
	261	SUZUKI, A., AND IRL M. 1986. Approximation of a tessellation of the plane by a Voronoi diagram. J. Operations Res. Soc. Japan 29, 69-96.
	262	TANEMURA, M., OGAWA, T., AND OGITA, N. 1983. A new algorithm for three-dimensional Voronoi tessellation. J. Comput. Phys. 51,191-207.
	263	T~SKI, A. 1951. A decision method for elementary algebra and geometry. Univ. of California Press, Berkeley, Calif.
	264	THmSSEN, A. H. 1911. Precipitation average for large area. Monthly Weather Rev. 39, 1082-1084.
	265	TOKUYAMA, T. 1988. Deformation of merged Voronoi diagrams with translation. Rep. TR- 88-0049, IBM Tokyo Research Lab.
	266	TOUSSA~NT, G. T. 1980. The relative neighborhood graph of a finite planar set. Pattern Recogn. 12, 261-268.
	267	TOUSSAINT, G. T., ANn BHATTACHARYA, B. K. 1981. On geometric algorithms that use the furthestpoint Voronoi diagram. Rep. 81-3, McGill Univ., Montreal, Quebec, Canada.
	268	TUOMIN~N, O. 1949. Das EinfiuBgebeit der Stadt Turku ins System der Einfiuflgebiete SW--Finnlands. Fennia 71-5, 1-138.
	269	URQUHART, R. 1980. A note on the computation of subgraphs of the Delaunay triangulation. Rep., Univ. of Glasgow, U.K.
	270	Pravin M. Vaidya, Minimum spanning trees in k-dimensional space, SIAM Journal on Computing, v.17 n.3, p.572-582, June 1988 [doi>10.1137/0217035]
	271	Pravin Vaidya, Geometry helps in matching, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.422-425, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62253]
	272	VORONOI, M. G. 1908. Nouvelles applications des parametres continus a la theorie des formes quadratiques. J. Reine Angew. Math. 134, 198-287.
	273	C. Wang , L. Schubert, An optimal algorithm for constructing the Delaunay triangulation of a set of line segments, Proceedings of the third annual symposium on Computational geometry, p.223-232, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41982]
	274	WATSON, D. F. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24, 167-172.
	275	WEAmE, D., ANn RWmR, N. 1984. Soap, cells, and statistics--random patterns in two dimensions. Contemp. Phys. 25, 59-99.
	276	WmTELEY, W. 1979. Realizability of polyhedra. Structural Topol. 1, 46-58.
	277	P. Widmayer , Y. F. Wu , C. K. Wong, On some distance problems in fixed orientations, SIAM Journal on Computing, v.16 n.4, p.728-746, Aug. 1987 [doi>10.1137/0216049]
	278	WIGNER, E., AND SEITZ, F. 1933. On the constitution of metallic sodium. Phys. Rev. 43, 804-810.
	279	WmLIAMS, R. E. 1968. Space-filling polyhedron: Its relation to aggregates of soap bubbles, plant cells, and metal crystalites. Science 161, 276-277.
	280	YAO, A. C. 1975. An O(E log log V) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4, 21-23.
	281	YAO, A. C. 1982. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11,721-736.
	282	YAP, C. K. 1987. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete Comput. Geom. 2, 365-393.