DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.28

Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences

Authors: Stefan Funke and Felix Weitbrecht

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

Given an ordered sequence of points P = {p₁, p₂, … , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O(|T|log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Θ(nlog n).

Cite as

Stefan Funke and Felix Weitbrecht. Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.ISAAC.2020.28,
  author =	{Funke, Stefan and Weitbrecht, Felix},
  title =	{{Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.28},
  URN =		{urn:nbn:de:0030-drops-133725},
  doi =		{10.4230/LIPIcs.ISAAC.2020.28},
  annote =	{Keywords: Computational Geometry, Delaunay Triangulation, Randomized Analysis}
}

Search Results

Documents authored by Weitbrecht, Felix

Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences

Abstract

Cite as

Thanks for your feedback!

Could not send message