Olivier Devillers, Stefan Meiser, Monique Teillaud  Home/Search
Context Related
| inria.fr/INRIA/publicat...RR1349.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: indiana.edu/pub/ucstri/index (more) Homepages: O.Devillers S.Meiser [2] M.Teillaud HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: The Delaunay Tree is a hierarchical data structure that has been introduced in [6] and analyzed in [7,4]. For a given set of sites S in the plane and an order of insertion for these sites, the Delaunay Tree stores all the successive Delaunay triangulations. As proved before, the Delaunay Tree allows the insertion of a site in logarithmic expected time and linear expected space, when the insertion sequence is randomized. (Update)
Context of citations to this paper: More
.... of insertion, of ensuring an O(log 2 n) location time for any point, and of allowing deletions in an easier way than the Delaunay tree [DMT92]. However, the additional memory is still important and the location structure is not especially simple. In 1996, Mcke, Saias and Zhu...
...with 6 unknowns, and a unique solution if the points are noncollinear. Thus, we make use of the Delaunay triangulation as implemented by [3] on the first frame and triangulate the second frame by points corresponding. Furthermore we assume that (C u ; C v ; a; b; c; d) are...
Cited by: More
Towards Dynamic Randomized Algorithms in Computational Geometry - Teillaud (1992) (Correct)
Four Results on Randomized Incremental Constructions - Clarkson, Mehlhorn, Seidel (1993) (Correct)
Using the Voronoi Tessellation for Grouping Words and.. - Burge, Monagan (1997) (Correct)
Similar documents (at the sentence level):
65.6%: Fully Dynamic Delaunay Triangulation in Logarithmic.. - Devillers, Meiser.. (1992) (Correct)
Active bibliography (related documents): More All
0.3: Dog Bites Postman: Point Location in the Moving Voronoi.. - Devillers, Golin (1994) (Correct)
0.3: On The Randomized Construction Of The Delaunay Tree - Boissonnat, Teillaud (1991) (Correct)
0.3: Randomization Yields Simple O(n log* n) Algorithms for Difficult .. - Devillers (1992) (Correct)
Similar documents based on text: More All
1.4: Robust and efficient implementation of the Delaunay tree - Devillers (1992) (Correct)
0.9: A Semi-Dynamic Construction of Higher Order.. - Boissonnat.. (1993) (Correct)
0.9: A Semi-Dynamic Construction of Higher Order Voronoi.. - Boissonnat.. (1993) (Correct)
Related documents from co-citation: More All
14: Randomized incremental construction of Delaunay and Voronoi diagrams (context) - Guibas, Knuth et al. - 1992
11: Applications of random sampling to on-line algorithms in computational geometry - Boissonnat, Devillers et al. - 1992
10: Applications of random sampling in computational geometry - Clarkson, Shor - 1989
BibTeX entry: (Update)
O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes in Computer Science, pages 42--53. Springer-Verlag, 1991. http://citeseer.nj.nec.com/devillers91fully.html More
@techreport{ devillers90fully,
author = "O. Devillers and S. Meiser and M. Teillaud",
title = "Fully dynamic Delaunay triangulation in logarithmic expected time per operation",
number = "RR-1349",
year = "1990",
url = "citeseer.nj.nec.com/devillers91fully.html" }
Citations (may not include all citations):1102 Computational Geometry: an Introduction (context) - Preparata, Shamos - 1985
268 Applications of random sampling in computational geometry - Clarkson, Shor - 1989
219 Primitives for the manipulation of general subdivi- sions an.. (context) - Guibas, Stolfi - 1985
121 A sweepline algorithm for Voronoi diagrams (context) - Fortune - 1987
85 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1992
76 The design of dynamic data structures (context) - Overmars - 1983
69 A linear time algorithm for computing the Voronoi diagram of.. (context) - Aggarwal, Guibas et al. - 1989
49 Two algorithms for constructing a Delaunay triangulation (context) - Lee, Schachter - 1980
47 Applications of random sampling to on-line algorithms in com.. - Boissonnat, Devillers et al.
47 Backwards analysis of randomized geometric algorithms - Seidel - 1991
41 Four results on randomized incremental constructions - Clarkson, Mehlhorn et al. - 1992
31 the randomized construction of the Delaunay tree - Boissonnat, Telllaud
25 Discrete and Computational Geometry (context) - Mulmuley, in et al. - 1991
23 Design and implementation of an efficient priority queue (context) - Boas, Kaas et al. - 1977
21 Dynamic maintenance of geometric structure made easy (context) - Schwarzkopf - 1991
20 Computing Dirichlet tesselations in the plane (context) - Green, Sibson - 1978
20 Randomized multidimensional search trees: dynamic sampling (context) - Mulmuley - 1991
19 the construction of abstract Voronoi diagrams (context) - Mehlhorn, Meiser et al. - 1991
11 A semi-dynamic construction of higher order Voronoi diagrams.. - Boissonnat, Devillers et al. - 1990
10 Department of Computer Science (context) - Shamos, PhD - 1978
8 A simple on-line randomized incremental algorithm for comput.. (context) - Aurenhammer, Schwarzkopf - 1991
6 Dynamic point location in arrangements of hyperplanes (context) - Mulmuley, Sen - 1991
1 A hierarchical representation of objects: the De- launay Tre.. (context) - Boissonnat, Telllaud - 1986
1 The design and ananlysis of computer' algo- rithms (context) - Aho, Hopcroft et al. - 1983
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.indiana.edu/pub/ucstri/index): More
Environment Modelling for Mobile Robots: Neural Learning for.. - van Dam (1998) (Correct)
Broadcasting in Butterfly and DeBruijn Networks - Klasing, Monien, Peine, Stöhr (1992) (Correct)
ILFA - A Project in Experimental Logic Computation - Dunker, Flögel, Büning.. (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