---
_id: '18747'
abstract:
- lang: eng
text: We present a new ( O(n) ) algorithm to compute good orders for the point set
of a Delaunay triangulation of ( n ) points in the plane. Such a good order makes
reconstruction in ( O(n) ) time with a simple algorithm possible. In contrast
to the algorithm of Snoeyink and van Kreveld cite1, which is based on independent
sets, our algorithm uses a breadth first search (BFS) to obtain these orders.
Both approaches construct such orders by repeatedly removing a constant fraction
of vertices from the current triangulation. The advantage of the BFS approach
is that we can give significantly better bounds on the fraction of removed points
in a phase of the algorithm. We can prove that a single phase of our algorithm
removes at least ( frac13 ) of the points, even if we restrict the degree of the
points (at the time they are removed) to 6. We implemented and compared both algorithms.
Our algorithms is slightly faster and achieves about 15% better vertex data compression
when using a simple variable length code to encode the differences between two
consecutive vertices of the given order.
author:
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: 'Sohler C. Fast Reconstruction of Delaunay Triangulations. In: *Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99)*. ; 1999:136-141.'
apa: Sohler, C. (1999). Fast Reconstruction of Delaunay Triangulations. In *Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99)* (pp.
136–141).
bibtex: '@inproceedings{Sohler_1999, title={Fast Reconstruction of Delaunay Triangulations},
booktitle={Proceedings of the 11th Canadian Conference on Computational Geometry
( CCCG’99)}, author={Sohler, Christian}, year={1999}, pages={136–141} }'
chicago: Sohler, Christian. “Fast Reconstruction of Delaunay Triangulations.” In
*Proceedings of the 11th Canadian Conference on Computational Geometry ( CCCG’99)*,
136–41, 1999.
ieee: C. Sohler, “Fast Reconstruction of Delaunay Triangulations,” in *Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99)*, 1999,
pp. 136–141.
mla: Sohler, Christian. “Fast Reconstruction of Delaunay Triangulations.” *Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99)*, 1999,
pp. 136–41.
short: 'C. Sohler, in: Proceedings of the 11th Canadian Conference on Computational
Geometry ( CCCG’99), 1999, pp. 136–141.'
date_created: 2020-09-01T10:43:10Z
date_updated: 2020-09-01T10:44:13Z
department:
- _id: '63'
language:
- iso: eng
page: 136-141
publication: Proceedings of the 11th Canadian Conference on Computational Geometry
( CCCG'99)
status: public
title: Fast Reconstruction of Delaunay Triangulations
type: conference
user_id: '15415'
year: '1999'
...