Geoff Leach  Home/Search
Context Related
| rmit.edu.au/~gl/res...paper_short.ps.gz rmit.edu.au/~gl/res...paper_short.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: rmit.edu.au/~gl/resear...delaunay (more) Homepages: G.Leach [2] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: We present results of an empirical investigation into the performance of two O(nlogn) worst-case optimal Delaunay triangulation algorithms: a divide-andconquer algorithm and a plane-sweep algorithm. We present improvements which give a factor of 4-5 speedup to the divide-and-conquer algorithm and a factor of 13-16 speed-up to the plane-sweep algorithm. Experiments using our improved implementations of both algorithms show the plane-sweep algorithm to be slightly faster (about 20%) than the... (Update)
Context of citations to this paper: More
.... of the algorithm is O(n log n) The sweepline algorithm is due to Fortune [9] In a comparison with divide and conquer, Leach [18] has optimized both algorithms and measured execution speed. According to Leach, the sweepline algorithm is the fastest, but also appears to...
Cited by: More
Automatic surface reconstruction from point sets in space - Attene, Spagnuolo (2000) (Correct)
Anisotropic Mesh Generation with Particles - Bossen (1996) (Correct)
Active bibliography (related documents): More All
0.3: Numerical Stability of Algorithms for Line Arrangements - Fortune, Milenkovic (1991) (Correct)
0.3: Cache Performance of Indexing Data Structures - Macdonald, Zhao (1999) (Correct)
0.0: Voronoi Diagrams and Delaunay Triangulations - Fortune (1992) (Correct)
Similar documents based on text: More All
0.1: Fast Algorithms for k-word Proximity Search - IMAI (2001) (Correct)
0.1: Text Retrieval by using k-word Proximity Search - Sadakane, Imai (1999) (Correct)
0.1: Finding Meaningful Regions Containing Given Keywords from.. - Sadakane, Imai (Correct)
BibTeX entry: (Update)
Geoff Leach. Improving worst-case optimal Delaunay triangulation algorithms. In 4th Canadian Conference on Computational Geometry, 1992. http://citeseer.nj.nec.com/leach92improving.html More
@inproceedings{ leach92improving,
author = "Geoff Leach",
title = "Improving Worst-Case Optimal {Delaunay} Triangulation Algorithms",
booktitle = "4th Canadian Conference on Computational Geometry",
year = "1992",
url = "citeseer.nj.nec.com/leach92improving.html" }
Citations (may not include all citations):1102 Computational Geometry - an Introduction (context) - Preparata, Shamos - 1985
417 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
411 Computational Geometry (context) - Shamos - 1977
219 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
121 A Sweepline Algorithm for Voronoi Diagrams (context) - Fortune - 1987
58 An Empirical Comparison of Priority-Queue and Event-Set Impl.. (context) - Jones - 1986
49 Two Algorithms for Constructing Delaunay Triangulations (context) - Lee, Schachter - 1980
42 A Polyhedron Representation for Computer Vision (context) - Baumgart - 1975
35 Efficient Delaunay Triangulation Using Rational Arithmetic (context) - Karasick, Lieber et al. - 1990
27 Self-adjusting heaps (context) - Sleator, Tarjan - 1986
21 A Faster Divide-and-Conquer Algorithm for Constructing Delau.. (context) - Dwyer - 1987
3 th Annual Symposium on Foundations of Computer Science (context) - Guibas, Sedgewick et al. - 1978
1 A Sweepcircle Algorithm for Voronoi Diagrams (context) - Dehne, Klein - 1987
1 th IEEE Symposium on Foundations of Computer Science (context) - Shamos, Hoey et al. - 1977
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