4 Search Results for "Junginger, Kolja"

Document
DOI: 10.4230/LIPIcs.SoCG.2025.12
Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

Authors: Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a set S of n colored sites, each s ∈ S associated with a distance-to-site function δ_s : ℝ² → ℝ, we consider two distance-to-color functions for each color: one takes the minimum of δ_s for sites s ∈ S in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-k color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound 4k(n-k)-2n on the total number of vertices in both the minimal and maximal order-k color diagrams for a wide class of distance functions δ_s that satisfy certain conditions, including the case of point sites S under convex distance functions and the L_p metric for any 1 ≤ p ≤ ∞. For the L_1 (or, L_∞) metric, and other convex polygonal metrics, we show that the order-k minimal diagram of point sites has O(min{k(n-k), (n-k)²}) complexity, while its maximal counterpart has O(min{k(n-k), k²}) complexity. To obtain these combinatorial results, we extend the Clarkson-Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored j-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present iterative algorithms to compute higher-order color Voronoi diagrams.
Cite as

Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou. Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.SoCG.2025.12,
  author =	{Bae, Sang Won and Oliver, Nicolau and Papadopoulou, Evanthia},
  title =	{{Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.12},
  URN =		{urn:nbn:de:0030-drops-231647},
  doi =		{10.4230/LIPIcs.SoCG.2025.12},
  annote =	{Keywords: higher-order Voronoi diagrams, color Voronoi diagrams, Hausdorff Voronoi diagrams, colored j-facets, arrangements, Clarkson-Shor technique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.52
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.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
DOI: 10.4230/LIPIcs.ESA.2021.54
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
DOI: 10.4230/LIPIcs.SoCG.2018.50
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.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 Type
  • 4 Document/PDF
  • 1 Document/HTML

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

  • Refine by Author
  • 4 Papadopoulou, Evanthia
  • 2 Junginger, Kolja
  • 1 Bae, Sang Won
  • 1 Mantas, Ioannis
  • 1 Oliver, Nicolau
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

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

  • Refine by Keyword
  • 1 Abstract Voronoi diagram
  • 1 Clarkson-Shor technique
  • 1 Delaunay’s theorem
  • 1 Fermat point
  • 1 Hausdorff Voronoi diagrams
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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