Christophe Lemaire, Jean-Michel Moreau  Home/Search
Context
Related
| toronto.edu/cgibin/Dow...paper44.ps.gz lisse.emse.fr/PUBL...lmcccg1997.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: toronto.edu/cccg/cccg97/pape...44 (more) Homepages: J.Moreau HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: This paper exploits the notion of "unfinished sites" in the average-case analysis of k-dimensional divideand -conquer algorithms. This general result is then applied to the 2D case, and it is shown that the divide-and-conquer construction of the Delaunay triangulation of a set of planar points quasi-uniformly distributed in a square may be done in expected linear time after a two-directional preprocessing sort. This method is readily implemented, and, as shown by the easily reproduced results... (Update)
Active bibliography (related documents): More All
0.6: Efficient Parallel Algorithms for Closest Point Problems - Peter Su (1994) (Correct)
0.5: A Comparison of Sequential Delaunay Triangulation Algorithms - Su, Drysdale (1996) (Correct)
0.4: Voronoi Diagrams and Delaunay Triangulations - Fortune (1992) (Correct)
Users who viewed this document also viewed: More All
0.1: Querying Documents in Object Databases - Abiteboul, Cluet, Christophides.. (1997) (Correct)
0.1: Efficient Algorithms for Robust Feature Matching - Mount, Netanyahu, Le Moigne (1998) (Correct)
0.1: The Linux Kernel - Rusling (1999) (Correct)
Similar documents based on text: More All
0.5: Recipes for Interactive Learning - With Hints For (Correct)
0.4: Fast Delaunay point location with search structures - Luc Devroye Christophe (Correct)
0.2: Elan: User Manual - Borovansky, Cirstea, Dubois.. (2000) (Correct)
BibTeX entry: (Update)
@misc{ lemaire-analysis,
author = "Christophe Lemaire and Jean-Michel Moreau",
title = "Analysis of a class of k-dimensional merge procedures, with an application
to 2D Delaunay Triangulation in expected linear time after two-directional
sorting (Extended Abstract)",
url = "citeseer.nj.nec.com/95461.html" }
Citations (may not include all citations):279 Multidimensional binary search trees used for associated sea.. (context) - Bentley - 1975
219 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
49 Two algorithms for constructing a Delaunay triangulation (context) - Lee, Schachter - 1980
34 Higher-Dimensional Voronoi Diagrams in Linear Expected Time (context) - Dwyer - 1991
21 A faster divide-and-conquer algorithm for constructing Delau.. (context) - Dwyer - 1987
12 The expected extremes in a Delaunay triangulation - Bern, Eppstein et al. - 1991
10 Delaunay triangulation and the convex hull of n points in ex.. (context) - Maus - 1984
5 Constructing Delaunay triangulations by merging buckets in q.. (context) - Katajainen, Koppinen - 1988
5 Improvements of the incremental method for the Voronoi diagr.. (context) - Ohya, Iti et al. - 1984
1 convexes et polytopes (context) - Berger - 1974
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