3 Search Results for "Junginger, Kolja"


Document
Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications

Authors: Evanthia Papadopoulou

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
Any system of bisectors (in the sense of abstract Voronoi diagrams) defines an arrangement of simple curves in the plane. We define Voronoi-like graphs on such an arrangement, which are graphs whose vertices are locally Voronoi. A vertex v is called locally Voronoi, if v and its incident edges appear in the Voronoi diagram of three sites. In a so-called admissible bisector system, where Voronoi regions are connected and cover the plane, we prove that any Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be seen as an abstract dual version of Delaunay’s theorem on (locally) empty circles. Further, we define Voronoi-like cycles in an admissible bisector system, and show that the Voronoi-like graph induced by such a cycle C is a unique tree (or a forest, if C is unbounded). In the special case where C is the boundary of an abstract Voronoi region, the induced Voronoi-like graph can be computed in expected linear time following the technique of [Junginger and Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm constructs the Voronoi-like graph of a cycle C′ on the same set (or subset) of sites, which may equal C or be enclosed by C. Overall, the technique computes abstract Voronoi (or Voronoi-like) trees and forests in linear expected time, given the order of their leaves along a Voronoi-like cycle. We show a direct application in updating a constraint Delaunay triangulation in linear expected time, after the insertion of a new segment constraint, simplifying upon the result of [Shewchuk and Brown CGTA 2015].

Cite as

Evanthia Papadopoulou. Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{papadopoulou:LIPIcs.SoCG.2023.52,
  author =	{Papadopoulou, Evanthia},
  title =	{{Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.52},
  URN =		{urn:nbn:de:0030-drops-179024},
  doi =		{10.4230/LIPIcs.SoCG.2023.52},
  annote =	{Keywords: Voronoi-like graph, abstract Voronoi diagram, Delaunay’s theorem, Voronoi tree, linear-time randomized algorithm, constraint Delaunay triangulation}
}
Document
Certified Approximation Algorithms for the Fermat Point and n-Ellipses

Authors: Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.

Cite as

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Certified Approximation Algorithms for the Fermat Point and n-Ellipses. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{junginger_et_al:LIPIcs.ESA.2021.54,
  author =	{Junginger, Kolja and Mantas, Ioannis and Papadopoulou, Evanthia and Suderland, Martin and Yap, Chee},
  title =	{{Certified Approximation Algorithms for the Fermat Point and n-Ellipses}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{54:1--54:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.54},
  URN =		{urn:nbn:de:0030-drops-146359},
  doi =		{10.4230/LIPIcs.ESA.2021.54},
  annote =	{Keywords: Fermat point, n-ellipse, subdivision, approximation, certified, algorithms}
}
Document
Deletion in Abstract Voronoi Diagrams in Expected Linear Time

Authors: Kolja Junginger and Evanthia Papadopoulou

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem for a long time. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under an insertion operation, thus, enabling its use in incremental constructions.

Cite as

Kolja Junginger and Evanthia Papadopoulou. Deletion in Abstract Voronoi Diagrams in Expected Linear Time. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{junginger_et_al:LIPIcs.SoCG.2018.50,
  author =	{Junginger, Kolja and Papadopoulou, Evanthia},
  title =	{{Deletion in Abstract Voronoi Diagrams in Expected Linear Time}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.50},
  URN =		{urn:nbn:de:0030-drops-87639},
  doi =		{10.4230/LIPIcs.SoCG.2018.50},
  annote =	{Keywords: Abstract Voronoi diagram, linear-time algorithm, update after deletion, randomized incremental algorithm}
}
  • Refine by Author
  • 3 Papadopoulou, Evanthia
  • 2 Junginger, Kolja
  • 1 Mantas, Ioannis
  • 1 Suderland, Martin
  • 1 Yap, Chee

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Abstract Voronoi diagram
  • 1 Delaunay’s theorem
  • 1 Fermat point
  • 1 Voronoi tree
  • 1 Voronoi-like graph
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021
  • 1 2023

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