Search Results

Documents authored by Aurenhammer, Franz

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.30
Piecewise-Linear Farthest-Site Voronoi Diagrams

Authors: Franz Aurenhammer, Evanthia Papadopoulou, and Martin Suderland

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Voronoi diagrams induced by distance functions whose unit balls are convex polyhedra are piecewise-linear structures. Nevertheless, analyzing their combinatorial and algorithmic properties in dimensions three and higher is an intriguing problem. The situation turns easier when the farthest-site variants of such Voronoi diagrams are considered, where each site gets assigned the region of all points in space farthest from (rather than closest to) it. We give asymptotically tight upper and lower worst-case bounds on the combinatorial size of farthest-site Voronoi diagrams for convex polyhedral distance functions in general dimensions, and propose an optimal construction algorithm. Our approach is uniform in the sense that (1) it can be extended from point sites to sites that are convex polyhedra, (2) it covers the case where the distance function is additively and/or multiplicatively weighted, and (3) it allows an anisotropic scenario where each site gets allotted its particular convex distance polytope.
Cite as

Franz Aurenhammer, Evanthia Papadopoulou, and Martin Suderland. Piecewise-Linear Farthest-Site Voronoi Diagrams. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2021.30,
  author =	{Aurenhammer, Franz and Papadopoulou, Evanthia and Suderland, Martin},
  title =	{{Piecewise-Linear Farthest-Site Voronoi Diagrams}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{30:1--30:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.30},
  URN =		{urn:nbn:de:0030-drops-154633},
  doi =		{10.4230/LIPIcs.ISAAC.2021.30},
  annote =	{Keywords: Voronoi diagram, farthest-site, polyhedral distance, polyhedral sites, general dimensions}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.60
Partially Walking a Polygon

Authors: Franz Aurenhammer, Michael Steinkogler, and Rolf Klein

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.
Cite as

Franz Aurenhammer, Michael Steinkogler, and Rolf Klein. Partially Walking a Polygon. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 60:1-60:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2018.60,
  author =	{Aurenhammer, Franz and Steinkogler, Michael and Klein, Rolf},
  title =	{{Partially Walking a Polygon}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{60:1--60:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.60},
  URN =		{urn:nbn:de:0030-drops-100089},
  doi =		{10.4230/LIPIcs.ISAAC.2018.60},
  annote =	{Keywords: Polygon, guard walk, visibility}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.7
Voronoi Diagrams for Parallel Halflines and Line Segments in Space

Authors: Franz Aurenhammer, Bert Jüttler, and Günter Paulini

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We consider the Euclidean Voronoi diagram for a set of $n$ parallel halflines in 3-space. A relation of this diagram to planar power diagrams is shown, and is used to analyze its geometric and topological properties. Moreover, an easy-to-implement space sweep algorithm is proposed that computes the Voronoi diagram for parallel halflines at logarithmic cost per face. Previously only an approximation algorithm for this problem was known. Our method of construction generalizes to Voronoi diagrams for parallel line segments, and to higher dimensions.
Cite as

Franz Aurenhammer, Bert Jüttler, and Günter Paulini. Voronoi Diagrams for Parallel Halflines and Line Segments in Space. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 7:1-7:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2017.7,
  author =	{Aurenhammer, Franz and J\"{u}ttler, Bert and Paulini, G\"{u}nter},
  title =	{{Voronoi Diagrams for Parallel Halflines and Line Segments in Space}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{7:1--7:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.7},
  URN =		{urn:nbn:de:0030-drops-82157},
  doi =		{10.4230/LIPIcs.ISAAC.2017.7},
  annote =	{Keywords: Voronoi diagram, line segments, space-sweep algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact