--- _id: '4026' abstract: - lang: eng text: 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. acknowledgement: National Science Foundation under Grant CCR-8921421, Alan T. Waterman award, Grant CCR-9118874. article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Nimish full_name: Shah, Nimish last_name: Shah citation: ama: Edelsbrunner H, Shah N. Incremental topological flipping works for regular triangulations. Algorithmica. 1996;15(3):223-241. doi:10.1007/BF01975867 apa: Edelsbrunner, H., & Shah, N. (1996). Incremental topological flipping works for regular triangulations. Algorithmica. Springer. https://doi.org/10.1007/BF01975867 chicago: Edelsbrunner, Herbert, and Nimish Shah. “Incremental Topological Flipping Works for Regular Triangulations.” Algorithmica. Springer, 1996. https://doi.org/10.1007/BF01975867. ieee: H. Edelsbrunner and N. Shah, “Incremental topological flipping works for regular triangulations,” Algorithmica, vol. 15, no. 3. Springer, pp. 223–241, 1996. ista: Edelsbrunner H, Shah N. 1996. Incremental topological flipping works for regular triangulations. Algorithmica. 15(3), 223–241. mla: 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. short: H. Edelsbrunner, N. Shah, Algorithmica 15 (1996) 223–241. date_created: 2018-12-11T12:06:31Z date_published: 1996-03-01T00:00:00Z date_updated: 2022-08-09T09:46:07Z day: '01' doi: 10.1007/BF01975867 extern: '1' intvolume: ' 15' issue: '3' language: - iso: eng month: '03' oa_version: None page: 223 - 241 publication: Algorithmica publication_identifier: issn: - 0178-4617 publication_status: published publisher: Springer publist_id: '2099' quality_controlled: '1' scopus_import: '1' status: public title: Incremental topological flipping works for regular triangulations type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 15 year: '1996' ...