14 Search Results for "Aurenhammer, Franz"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.15
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.
Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.16
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Authors: Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).
Cite as

Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber. Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2026.16,
  author =	{Bjerkevik, H\r{a}vard Bakke and Dorfer, Joseph and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
  title =	{{Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.16},
  URN =		{urn:nbn:de:0030-drops-258225},
  doi =		{10.4230/LIPIcs.SoCG.2026.16},
  annote =	{Keywords: Non-crossing, spanning tree, plane graph, flip graph, reconfiguration, diameter, complexity, NP-hard, edge exchange, compatible flip, rotation, happy edge property}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.40
Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface

Authors: Loïc Dubois

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Every surface that is intrinsically polyhedral can be represented by a portalgon: a collection of polygons in the Euclidean plane with some pairs of equally long edges abstractly identified. While this representation is arguably simpler than meshes (flat polygons in ℝ³ forming a surface), it has unbounded happiness: a shortest path in the surface may visit the same polygon arbitrarily many times. This pathological behavior is an obstacle towards efficient algorithms. On the other hand, Löffler, Ophelders, Staals, and Silveira [SoCG 2023] recently proved that the (intrinsic) Delaunay triangulations have bounded happiness. In this paper, given a closed polyhedral surface S, represented by a triangular portalgon T, we provide an algorithm to compute the Delaunay triangulation of S whose vertices are the singularities of S (the points whose surrounding angle is distinct from 2π). The time complexity of our algorithm is polynomial in the number of triangles and in the logarithm of the aspect ratio r of T. Within our model of computation, we show that the dependency in log r is unavoidable. Our algorithm can be used to pre-process a triangular portalgon before computing shortest paths on its surface, and to determine whether the surfaces of two triangular portalgons are isometric.
Cite as

Loïc Dubois. Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dubois:LIPIcs.SoCG.2026.40,
  author =	{Dubois, Lo\"{i}c},
  title =	{{Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.40},
  URN =		{urn:nbn:de:0030-drops-258460},
  doi =		{10.4230/LIPIcs.SoCG.2026.40},
  annote =	{Keywords: Polyhedral surface, intrinsic Delaunay triangulation, algorithmic complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.84
The Voronoi Diagram of Four Lines in ℝ³

Authors: Evanthia Papadopoulou and Zeyu Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We consider the Voronoi diagram of lines in ℝ³ under the Euclidean metric, and give a full classification of its structure in the base case of four lines in general position. We first show that the number of vertices in the Voronoi diagram of four lines in general position is always even, between 0 and 8, and all such numbers can be realized. We identify a key structure for the diagram formation, called a twist, which is a pair of consecutive intersections among trisector branches; only two types of twists are possible, so-called full and partial twists. A full twist is a purely local structure, which can be inserted or removed without affecting the rest of the diagram. Assuming no full twists, the nearest and the farthest Voronoi diagrams of four lines, each have 15 distinct topologies, which are in one-to-one correspondence; the two-dimensional faces are all unbounded, and the total number of vertices is at most six. The unbounded features of the farthest diagram, encoded in a two-dimensional spherical map, are also in one-to-one correspondence. The identified topologies are all realizable. Any Voronoi diagram of four lines in general position in ℝ³ can be obtained from one of these topologies by inserting full twists; each twist induces a bounded face of exactly two vertices in both the nearest and farthest diagrams. We obtain the classification by an exhaustive search algorithm using some new structural and combinatorial observations of line Voronoi diagrams.
Cite as

Evanthia Papadopoulou and Zeyu Wang. The Voronoi Diagram of Four Lines in ℝ³. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{papadopoulou_et_al:LIPIcs.SoCG.2026.84,
  author =	{Papadopoulou, Evanthia and Wang, Zeyu},
  title =	{{The Voronoi Diagram of Four Lines in \mathbb{R}³}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{84:1--84:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.84},
  URN =		{urn:nbn:de:0030-drops-258916},
  doi =		{10.4230/LIPIcs.SoCG.2026.84},
  annote =	{Keywords: Voronoi diagram, lines, three dimensions, structural properties}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.98
Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition)

Authors: Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Floodlight illumination problems are art-gallery variants, where a target domain needs to be illuminated by guards, each associated with a field of view. The rotating rays Voronoi diagram is a Voronoi diagram with rays as sites under the angular distance. There is a natural connection of this Voronoi structure with the problem of finding the minimum aperture such that a given set of uniform aperture floodlights illuminates a target domain. In this work we present an interactive visualization software for such problems, supporting different angular distances, namely, oriented and unoriented versions, and for different domains, namely, the plane and simple polygons.
Cite as

Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland. Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 98:1-98:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.SoCG.2026.98,
  author =	{Alegr{\'\i}a, Carlos and Mantas, Ioannis and Savi\'{c}, Marko and Suderland, Martin},
  title =	{{Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{98:1--98:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.98},
  URN =		{urn:nbn:de:0030-drops-259048},
  doi =		{10.4230/LIPIcs.SoCG.2026.98},
  annote =	{Keywords: rotating rays Voronoi diagram, oriented angular distance, unoriented angular distance, Brocard angle, floodlight illumination, coverage problems, visualization software}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.31
Delaunay Triangulations with Predictions

Authors: Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.
Cite as

Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos. Delaunay Triangulations with Predictions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ITCS.2026.31,
  author =	{Cabello, Sergio and Chan, Timothy M. and Giannopoulos, Panos},
  title =	{{Delaunay Triangulations with Predictions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31},
  URN =		{urn:nbn:de:0030-drops-253186},
  doi =		{10.4230/LIPIcs.ITCS.2026.31},
  annote =	{Keywords: Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.47
Reconfigurations of Plane Caterpillars and Paths (Poster Abstract)

Authors: Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Let S be a point set in the plane, and let 𝒫(S) and 𝒞(S) be the sets of all plane spanning paths and caterpillars on S. We study reconfiguration operations on 𝒫(S) and 𝒞(S). In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when S is in convex position. If S is in general position, we show that the rotation, compatible flip and flip graphs of 𝒞(S) are connected while the slide graph is sometimes disconnected, but always has a component of size 1/4(3ⁿ-1). We then study sizes of connected components in reconfiguration graphs of plane spanning paths. In this direction, we show that no component of size at most 7 can exist in the flip graph on 𝒫(S).
Cite as

Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić. Reconfigurations of Plane Caterpillars and Paths (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 47:1-47:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.47,
  author =	{Anti\'{c}, Todor and Gamboa Quintero, Guillermo and Gli\v{s}i\'{c}, Jelena},
  title =	{{Reconfigurations of Plane Caterpillars and Paths}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{47:1--47:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.47},
  URN =		{urn:nbn:de:0030-drops-250337},
  doi =		{10.4230/LIPIcs.GD.2025.47},
  annote =	{Keywords: reconfiguration graph, caterpillar, path, geometric graph}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.24
Computational Geometry with Probabilistically Noisy Primitive Operations

Authors: David Eppstein, Michael T. Goodrich, and Vinesh Sridhar

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.
Cite as

David Eppstein, Michael T. Goodrich, and Vinesh Sridhar. Computational Geometry with Probabilistically Noisy Primitive Operations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.WADS.2025.24,
  author =	{Eppstein, David and Goodrich, Michael T. and Sridhar, Vinesh},
  title =	{{Computational Geometry with Probabilistically Noisy Primitive Operations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24},
  URN =		{urn:nbn:de:0030-drops-242552},
  doi =		{10.4230/LIPIcs.WADS.2025.24},
  annote =	{Keywords: Computational geometry, noisy comparisons, random walks}
}
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.2025.43
On Spheres with k Points Inside

Authors: Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian

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

Abstract
We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.
Cite as

Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian. On Spheres with k Points Inside. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2025.43,
  author =	{Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza},
  title =	{{On Spheres with k Points Inside}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{43:1--43:12},
  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.43},
  URN =		{urn:nbn:de:0030-drops-231951},
  doi =		{10.4230/LIPIcs.SoCG.2025.43},
  annote =	{Keywords: Triangulations, higher-order Delaunay triangulations, hypertriangulations, Delone sets, k-sets, Worpitzky’s identity, hypersimplices}
}
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.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}
}
  • Refine by Type
  • 14 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 6 2026
  • 4 2025
  • 1 2023
  • 1 2021
  • 1 2018
  • Show More...

  • Refine by Author
  • 4 Papadopoulou, Evanthia
  • 3 Aurenhammer, Franz
  • 2 Suderland, Martin
  • 1 Alegría, Carlos
  • 1 Antić, Todor
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 3 Voronoi diagram
  • 1 Algorithms with Predictions
  • 1 Brocard angle
  • 1 Clarkson-Shor technique
  • 1 Computational geometry
  • 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