1 Search Results for "Paulini, G�nter"

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-dev.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}
}
  • Refine by Author
  • 1 Aurenhammer, Franz
  • 1 Jüttler, Bert
  • 1 Paulini, Günter

  • Refine by Classification

  • Refine by Keyword
  • 1 Voronoi diagram
  • 1 line segments
  • 1 space-sweep algorithm

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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