Olivier Devillers, Stefan Meiser, Monique Teillaud  Home/Search
Context Related
| inria.fr/prisme/pu...dmtfddtl92.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: sop.inria.fr/prism...publi_random (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 [7] and analyzed in [6, 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. In this paper, we describe an algorithm maintaining the Delaunay... (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):
67.1%: Fully Dynamic Delaunay Triangulation in Logarithmic.. - Devillers, Meiser.. (1991) (Correct)
Active bibliography (related documents): More All
0.4: On The Randomized Construction Of The Delaunay Tree - Boissonnat, Teillaud (1991) (Correct)
0.4: Dog Bites Postman: Point Location in the Moving Voronoi.. - Devillers, Golin (1994) (Correct)
0.3: Randomization Yields Simple O(n log* n) Algorithms for Difficult .. - Devillers (1992) (Correct)
Similar documents based on text: More All
0.6: Robust and efficient implementation of the Delaunay tree - Devillers (1992) (Correct)
0.5: Applications of Random Sampling to On-line.. - Boissonnat.. (1992) (Correct)
0.5: A Semi-Dynamic Construction of Higher Order.. - 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/article/devillers92fully.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/article/devillers92fully.html" }
Citations (may not include all citations):1114 Computational Geometry : an Introduction (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
124 A sweepline algorithm for Voronoi diagrams (context) - Fortune - 1987
85 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1992
79 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. - 1992
47 Backwards analysis of randomized geometric algorithms - Seidel - 1991
42 Four results on randomized incremental constructions - Clarkson, Mehlhorn et al. - 1992
31 the randomized construction of the Delaunay tree - Boissonnat, Teillaud
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
22 A hierarchical representation of objects: The Delaunay Tree (context) - Boissonnat, Teillaud - 1986
21 Dynamic maintenance of geometric structures made easy (context) - Schwarzkopf - 1991
20 the construction of abstract Voronoi diagrams (context) - Mehlhorn, Meiser et al. - 1991
20 Computing Dirichlet tesselations in the plane (context) - Green, Sibson - 1978
20 Randomized multidimensional search trees : Dynamic sampling (context) - Mulmuley - 1991
19 Fully dynamic Delaunay triangulation in logarithmic expected.. - Devillers, 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
9 of computer algorithms. Computer science and information pro.. (context) - Aho, Hopcroft et al. - 1983
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
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www-sop.inria.fr/prisme/personnel/teillaud/publi_random.html):
A Semi-Dynamic Construction of Higher Order Voronoi.. - Boissonnat.. (1993) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute