A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time

Abstract

We present a modification to the divide-and-conquer algorithm of Guibas & Stolfi [GS] for computing the Delaunay triangulation of n sites in the plane. The change reduces its T(n log n) expected running time to O(n log n) for a large class of distributions which includes the uniform distribution in the unit square. The modified algorithm is significantly easier to implement than the optimal linear-expected-time algorithm of Bentley, Weide & Yao [BWY]. Unlike the incremental methods of Ohya, Iri & Murota [OIM] and Maus [M] it has optimal O(n log log n) worst-case performance. The improvement extends to the composition of the Delaunay triangulation in the Lp metric for 1

Keywords

Divide and conquer algorithmsDelaunay triangulationBinary logarithmComputer scienceLog-log plotSimple (philosophy)Time complexityCombinatoricsAlgorithmMathematicsDiscrete mathematics

Affiliated Institutions

Carnegie Mellon University US

Related Publications

An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score

Sampath K. Kannan , Eugene W. Myers

In this paper, we present an $O(N^2 \log ^2 )$ algorithm for finding the two nonoverlapping substrings of a given string of length N which have the highest-scoring alignment bet...

1996 SIAM Journal on Computing 41 citations

All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings

Jeanette P. Schmidt

Weighted paths in directed grid graphs of dimension (m X n) can be used to model the string edit problem, which consists of obtaining optimal (weighted) alignments between subst...

1998 SIAM Journal on Computing 141 citations

Online facility location

Adam Meyerson

We consider the online variant of facility location, in which demand points arrive one at a time and we must maintain a set of facilities to service these points. We provide a r...

2001 252 citations

A rigorous time bound for factoring integers

H. W. Lenstra , Carl Pomerance

In this paper a probabilistic algorithm is exhibited that factors any positive integer<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math...

1992 Journal of the American Mathematical ... 112 citations

Improved time bounds for near-optimal sparse Fourier representations

Anna C. Gilbert , S. Muthukrishnan , Michael Strauss

•We study the problem of finding a Fourier representation R of m terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) ca...

2005 Proceedings of SPIE, the Internationa... 212 citations

Publication Info

Year: 1986
Type: article
Pages: 276-284
Citations: 26
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

OpenAlex

Cite This

APA Style

                            
                                    Rex A. Dwyer
                                
                            (1986). 
                            A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time. 
                            
                            , 276-284.
                            https://doi.org/10.1145/10515.10545

Identifiers

DOI: 10.1145/10515.10545