DELAUNAY TRIANGULATIONS IN THE PLANE WITH${\mathcal O} (\sqrt{N} \log N)$STORAGE REQUIREMENTS

A. Kartashov and R. Folk
Additional contact information
A. Kartashov: Institute for Theoretical Physics, University of Linz, Altenberger Str. 69, A-4040 Linz, Austria
R. Folk: Institute for Theoretical Physics, University of Linz, Altenberger Str. 69, A-4040 Linz, Austria

International Journal of Modern Physics C (IJMPC), 1995, vol. 06, issue 05, 639-649

Abstract: We present a straightforward iterative algorithm constructing the planar Delaunay triangulation in${\mathcal O} (\sqrt{N} \log N)$time. The algorithm proceeds iteratively by adding new points one by one to a partial point set pre-ordered by one coordinate and adjusting the partial diagram correspondingly. We introduce the techniques ofsafe fragments, showing that the larger part of a partial digram cannot be changed by adding further points; in the average case of a random point set the amount of information which need be stored in memory at any moment does not exceed${\mathcal O} (\sqrt{N} \log N)$. The computational overhead for the memory management is linear inN. In particular, this makes very large Delaunay triangulations (and Voronoi tessellations) accessible for simulations on personal computers.

Date: 1995
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S012918319500054X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:06:y:1995:i:05:n:s012918319500054x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S012918319500054X

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().