Steven Fortune  Home/Search
Context Related
| belllabs.com/cm/cs/who/sj...vddt.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: belllabs.com/cm/cs/who/sj...pubs (more) Homepages: S.Fortune [2] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: The Voronoi diagram is a fundamental structure in computationalgeometry and arises naturally in many different fields. This chapter surveys properties of the Voronoi diagram and its geometric dual, the Delaunay triangulation. The emphasis is on practical algorithms for the construction of Voronoi diagrams. 1 Introduction Let S be a set of n points in d-dimensional euclidean space E d . The points of S are called sites. The Voronoi diagram of S splits E d into regions with one region... (Update)
Context of citations to this paper: More
...The dimension of C is dim C = maxtor dims. The underlying space of C is [ J C = Jcc rr. Delaunay triangulation and Voronoi diagrams[23]. Let P = Pl, Pn be a set of points in 11 d. The Delaunay triangulation and Voronoi diagram can be defined as dual structures of the...
.... range queries, that is, for a set of sites in d d dimensional space (i.e. which site is nearest to a given query point [Fortune, 1992][O Rourke, 1998] An example VD is shown in Figure 5. The VD takes as input a set q of points in space called the sites, and...
Cited by: More
Proximity Structures for Geometric Graphs - Sanjiv Kapoor And (Correct)
Coverage in Wireless Ad Hoc Sensor Networks Xiang-Yang Li, .. - Ophir Frieder Fellow (Correct)
A strategy for analysis of (molecular) equilibrium .. - Hamprecht, Peter, .. (Correct)
Active bibliography (related documents): More All
1.4: Computational Geometry - Fortune (1994) (Correct)
0.8: Efficient Parallel Algorithms for Closest Point Problems - Peter Su (1994) (Correct)
0.8: A Comparison of Sequential Delaunay Triangulation Algorithms - Su, Drysdale (1996) (Correct)
Similar documents based on text: More All
0.4: CS20c Final Report by Zhaosheng (Joshua) Bao Delaunay.. - Theory Algorithm And (Correct)
0.3: The deldir Package - February Version Date (Correct)
0.2: Delaunay triangulation programs on surface data* - Sunghee Choi Nina (Correct)
Related documents from co-citation: More All
10: Mesh generation and optimal triangulation - BERN, EPPSTEIN - 1992
8: Voronoi diagrams --- a survey of a fundamental geometric data structure (context) - Aurenhammer - 1991
7: Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
BibTeX entry: (Update)
Fortune, S., Voronoi Diagrams and Delaunay triangulations, in Computing in Euclidean Geometry, D. Z. Du, F.Hwang (eds.), World Scientific Publ., 1992, 193--223. http://citeseer.nj.nec.com/article/fortune92voronoi.html More
@incollection{ fortune92voronoi,
author = "Fortune",
title = "Voronoi Diagrams and Delaunay Triangulations",
booktitle = "Computing in Euclidean Geometry, Edited by Ding-Zhu Du and Frank Hwang, World Scientific, Lecture Notes Series on Computing -- Vol. 1",
year = "1992",
url = "citeseer.nj.nec.com/article/fortune92voronoi.html" }
Citations (may not include all citations):1643 The Art of Computer Programming (context) - Knuth - 1969
429 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
420 Computational Geometry (context) - Preparata, Shamos - 1985
272 Applications of random sampling in computational geometry - Clarkson, Shor - 1989
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
203 Voronoi diagrams -- a survey of a fundamental geometric data.. (context) - Aurenhammer - 1991
124 Sweepline algorithms for Voronoi diagrams (context) - Fortune - 1987
111 Numerical Methods (context) - Dahlquist, Bjorck et al. - 1974
96 Convex Polytopes (context) - Grunbaum - 1967
85 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1990
76 Closest-point problems (context) - Shamos, Hoey - 1975
66 Verifiable implementations of geometric algorithms using fin.. (context) - Milenkovic - 1988
55 Optimal expected-time algorithms for closestpoint problems (context) - Bentley, Weide et al. - 1980
53 A geometric consistency theorem for a symbolic perturbation .. (context) - Yap - 1990
51 Incremental topological flipping works for regular triangula.. (context) - Edelsbrunner, Shah - 1992
48 dimensional Delaunay tessellation with application to Vorono.. (context) - Watson, n- - 1981
44 Computing Dirichlet tessellations (context) - Bowyer - 1981
42 Four results on randomized incremental constructions - Clarkson, Mehlhorn et al. - 1992
36 Efficient Delaunay triangulation using rational arithmetic (context) - Karasick, Lieber et al. - 1990
35 Voronoi diagrams from convex hulls (context) - Brown - 1979
34 Higher-dimensional Voronoi diagrams in linear expected time (context) - Dwyer - 1991
33 The problems of accuracy and robustness in geometric computa.. (context) - Hoffmann - 1989
33 A new statistical approach to geographic variation analysis (context) - Gabriel, Sokal - 1969
32 A general approach to removing degeneracies - Emiris, Canny - 1991
32 Stable maintenance of point-set triangulation in two dimensi.. (context) - Fortune - 1989
31 Construction of three-dimensional Delaunay triangulations us.. (context) - Joe - 1991
31 Computing Dirichlet tessellations in the plane (context) - Green, Sibson - 1977
31 Convex Polytopes and the Upper Bound Conjecture (context) - McMullen, Shephard - 1971
30 Three dimensional triangulations from local transformations (context) - Joe - 1989
28 Representing geometric structures in d-dimensions: topology .. (context) - Brisson - 1989
25 Symbolic treatment of geometric degeneracies (context) - Yap - 1990
22 An hierarchical representation of objects: the Delaunay tree (context) - Boissonnat, Teillaud - 1989
22 A sparse graph almost as good as the complete graph on point.. (context) - Vaidya - 1991
21 Optimality of the Delaunay triangulation in R d (context) - Rajan - 1991
21 A faster divide-and-conquer algorithm for constructing Delau.. (context) - Dwyer - 1987
19 There are planar graphs almost as good as the complete graph (context) - Chew - 1989
19 Voronoi diagrams and arrangements (context) - Edelsbrunner, Seidel - 1986
18 An optimal convex hull algorithm and new results on cuttings (context) - Chazelle - 1991
18 Randomized geometric algorithms - Clarkson
16 An Introduction to Convex Polytopes (context) - Brndsted - 1983
16 Mathematical Software III (context) - Lawson, for et al. - 1977
14 Encyclopedia of Mathematics and its Applications (context) - Santal'o, Geometry et al. - 1976
11 The Delaunay triangulation closely approximates the complete.. (context) - Keil, Gutwin - 1989
9 Toughness and Delaunay triangulations (context) - Dillencourt - 1990
8 Globally-equiangular triangulations of cocircular points in .. (context) - Mount, Saalfeld - 1988
7 dimensional spaces and n-dimensional generalized maps (context) - Lienhardt, n- - 1989
6 Recognizing Dirichlet tessellations (context) - Ash, Bolker - 1985
6 The complexity of Voronoi diagrams in higher dimension (context) - Seidel - 1982
5 a technique to cope with degenerate cases in geometric compu.. (context) - Edelsbrunner, Mucke et al. - 1990
5 Numerical stability of algorithms for Delaunay triangulation.. (context) - Fortune - 1992
5 Constructing Delaunay triangulations by merging buckets in q.. (context) - Katajainen, Koppinen - 1987
5 Improvements of the incremental method for the Voronoi diagr.. (context) - Ohya, Iri et al. - 1984
3 A note on Delaunay diagonal flips (context) - Fortune
2 edge length and number of vertices in crystal aggregates wit.. (context) - Meijering, area - 1953
2 A fast Voronoi-diagram with quaternary tree bucketing (context) - Ohya, Iri et al. - 1984
2 Combinatorial structure of Delaunay triangulations in the pl.. (context) - Dillencourt, Rivin et al. - 1991
2 Applications of random sampling to online algorithms in comp.. (context) - Boissonnat, Devillers et al. - 1990
2 and computer: the design and analysis of geometric algorithm.. (context) - Guibas, Stolfi et al. - 1988
1 private communication (context) - Dwyer
1 Generalized Dirichlet tessellations (context) - Ash, Bolker - 1986
1 Recognizing polytopical cell complexes and constructing proj.. (context) - Aurenhammer - 1987
1 Inscribable graphs (context) - Rivin, Smith - 1991
1 Constructing higher-dimensional convex hull algorithms at lo.. (context) - Seidel - 1986
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://cm.bell-labs.com/cm/cs/who/sjf/pubs.html): More
Topological beam tracing - Fortune (1999) (Correct)
Robustness issues in geometric algorithms - Fortune (1996) (Correct)
Static Analysis Yields Efficient Exact Integer Arithmetic.. - Fortune, Van Wyk (1996) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute