Incremental topological flipping works for regular triangulations

H. Edelsbrunner, N. Shah, Algorithmica 15 (1996) 223–241.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
A set of n weighted points in general position in R(d) defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at most O(n log n + n(inverted left perpendicular d/2 inverted right perpendicular)). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor log n more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.
Publishing Year
Date Published
1996-03-01
Journal Title
Algorithmica
Acknowledgement
National Science Foundation under Grant CCR-8921421, Alan T. Waterman award, Grant CCR-9118874.
Volume
15
Issue
3
Page
223 - 241
IST-REx-ID

Cite this

Edelsbrunner H, Shah N. Incremental topological flipping works for regular triangulations. Algorithmica. 1996;15(3):223-241. doi:10.1007/BF01975867
Edelsbrunner, H., & Shah, N. (1996). Incremental topological flipping works for regular triangulations. Algorithmica, 15(3), 223–241. https://doi.org/10.1007/BF01975867
Edelsbrunner, Herbert, and Nimish Shah. “Incremental Topological Flipping Works for Regular Triangulations.” Algorithmica 15, no. 3 (1996): 223–41. https://doi.org/10.1007/BF01975867.
H. Edelsbrunner and N. Shah, “Incremental topological flipping works for regular triangulations,” Algorithmica, vol. 15, no. 3, pp. 223–241, 1996.
Edelsbrunner H, Shah N. 1996. Incremental topological flipping works for regular triangulations. Algorithmica. 15(3), 223–241.
Edelsbrunner, Herbert, and Nimish Shah. “Incremental Topological Flipping Works for Regular Triangulations.” Algorithmica, vol. 15, no. 3, Springer, 1996, pp. 223–41, doi:10.1007/BF01975867.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar