28 Search Results for "Biniaz, Ahmad"

Document
DOI: 10.4230/LIPIcs.ESA.2025.57
Improved Hardness-Of-Approximation for Token-Swapping

Authors: Sam Hiken and Nicole Wein

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the token swapping problem, in which we are given a graph with an initial assignment of one distinct token to each vertex, and a final desired assignment (again with one token per vertex). The goal is to find the minimum length sequence of swaps of adjacent tokens required to get from the initial to the final assignment. The token swapping problem is known to be NP-complete. It is also known to have a polynomial-time 4-approximation algorithm. From the hardness-of-approximation side, it is known to be NP-hard to approximate with a ratio better than 1001/1000. Our main result is an improvement of the approximation ratio of the lower bound: We show that it is NP-hard to approximate with ratio better than 14/13. We then turn our attention to the 0/1-weighted version, in which every token has a weight of either 0 or 1, and the cost of a swap is the sum of the weights of the two participating tokens. Unlike standard token swapping, no constant-factor approximation is known for this version, and we provide an explanation. We prove that 0/1-weighted token swapping is NP-hard to approximate with ratio better than (1-ε) ln(n) for any constant ε > 0. Lastly, we prove two barrier results for the standard (unweighted) token swapping problem. We show that one cannot beat the current best known approximation ratio of 4 using a large class of algorithms which includes all known algorithms, nor can one beat it using a common analysis framework.
Cite as

Sam Hiken and Nicole Wein. Improved Hardness-Of-Approximation for Token-Swapping. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hiken_et_al:LIPIcs.ESA.2025.57,
  author =	{Hiken, Sam and Wein, Nicole},
  title =	{{Improved Hardness-Of-Approximation for Token-Swapping}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.57},
  URN =		{urn:nbn:de:0030-drops-245251},
  doi =		{10.4230/LIPIcs.ESA.2025.57},
  annote =	{Keywords: algorithms, token-swapping, hardness-of-approximation, lower-bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.75
An Improved Bound for Plane Covering Paths

Authors: Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.
Cite as

Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous. An Improved Bound for Plane Covering Paths. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 75:1-75:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.75,
  author =	{A. Akitaya, Hugo and Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Gavoille, Cyril and Iacono, John and Kleist, Linda and Smid, Michiel and Souvaine, Diane and Theocharous, Leonidas},
  title =	{{An Improved Bound for Plane Covering Paths}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{75:1--75:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.75},
  URN =		{urn:nbn:de:0030-drops-245432},
  doi =		{10.4230/LIPIcs.ESA.2025.75},
  annote =	{Keywords: Covering Path, Upper Bound, Simple Algorithm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.7
Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Authors: Sayan Bandyapadhyay and Eli Mitchell

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

Abstract
We study the Discrete Covering with Two Types of Radii problem motivated by its application in wireless networks. In this problem, the goal is to assign either small-range high frequency or large-range low frequency to each access point, maximizing the number of users in high-frequency regions while ensuring that each user is in the range of an access point. Unlike other weighted covering problems, our problem requires satisfying two simultaneous objectives, which calls for novel approaches that leverage the underlying geometry of the problem. In our work, we present two new algorithms: the first is a polynomial-time (2.5 + ε)-approximation, and the second is an exact algorithm for sparse instances, which is fixed-parameter tractable (FPT) in the number of large-radius disks. We also prove that such an FPT algorithm is impossible for general instances lacking sparsity, assuming the Exponential Time Hypothesis. Before our work, the best-known polynomial-time approximation factor was 4 for the problem. Our approximation algorithm results from a fine-grained classification of points that can contribute to the gain of a solution. Based on this classification, we design two sub-algorithms with interdependent guarantees to recover the respective class of points as gain. Our algorithm exploits further properties of Delaunay triangulations to achieve the improved bound. The FPT algorithm is based on branching that utilizes the sparsity of the instances to limit the overall search space.
Cite as

Sayan Bandyapadhyay and Eli Mitchell. Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.WADS.2025.7,
  author =	{Bandyapadhyay, Sayan and Mitchell, Eli},
  title =	{{Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{7:1--7:14},
  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.7},
  URN =		{urn:nbn:de:0030-drops-242386},
  doi =		{10.4230/LIPIcs.WADS.2025.7},
  annote =	{Keywords: Covering, Disks, Approximation, FPT}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.8
Tight Bounds on the Number of Closest Pairs in Vertical Slabs

Authors: Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid, and Csaba D. Tóth

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

Abstract
Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known.
Cite as

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid, and Csaba D. Tóth. Tight Bounds on the Number of Closest Pairs in Vertical Slabs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.WADS.2025.8,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Chung, Chaeyoon and De Carufel, Jean-Lou and Iacono, John and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D.},
  title =	{{Tight Bounds on the Number of Closest Pairs in Vertical Slabs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{8:1--8:14},
  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.8},
  URN =		{urn:nbn:de:0030-drops-242391},
  doi =		{10.4230/LIPIcs.WADS.2025.8},
  annote =	{Keywords: closest pair, vertical slab, data structure}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.9
Online Routing in Directed Yao₄^∞ Graphs

Authors: Prosenjit Bose, Jean-Lou De Carufel, and John Stuart

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

Abstract
The x⃑{Yao₄^∞} and x⃑{Yao₄} graphs are two families of directed geometric graphs whose vertices are points in the plane, and each vertex has up to four outgoing edges. Consider a horizontal and a vertical line through each vertex v, defining four quadrants around v. Then v has an outgoing edge to the closest vertex in each of its four quadrants. When the distance is measured using the Euclidean norm, the resulting graph is the x⃑{Yao₄} graph, whereas with the L_∞-norm, we obtain the x⃑{Yao^{∞}₄} graph, which is a sub-graph of the well-known L_∞-Delaunay graph. In this paper, we provide a local routing algorithm with routing ratio at most 85.22 for x⃑{Yao^{∞}₄} graphs. Prior to this work, no constant spanning or routing ratios for x⃑{Yao₄^∞} graphs were previously known. Now, x⃑{Yao₄^∞} graphs are the sparsest family of directed planar graphs supporting a competitive local routing strategy. Furthermore, we show that no local routing algorithm for x⃑{Yao₄^∞} graphs can have a routing ratio lower than 7+√2≈ 8.41. Moreover, we prove that the spanning ratio is at least 5+√2≈ 6.41 in the worst case. The techniques we develop in this paper also allow us to prove lower bounds of 7-√3+√{5-2√3}≈ 6.51 and 7+√2 for the spanning and routing ratios of x⃑{Yao₄}, respectively.
Cite as

Prosenjit Bose, Jean-Lou De Carufel, and John Stuart. Online Routing in Directed Yao₄^∞ Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.9,
  author =	{Bose, Prosenjit and De Carufel, Jean-Lou and Stuart, John},
  title =	{{Online Routing in Directed Yao₄^∞ Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{9:1--9:22},
  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.9},
  URN =		{urn:nbn:de:0030-drops-242404},
  doi =		{10.4230/LIPIcs.WADS.2025.9},
  annote =	{Keywords: Geometric Spanners, Yao Graphs, Local Routing Algorithms}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.10
On Geodesic Disks Enclosing Many Points

Authors: Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle

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

Abstract
Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem.
Cite as

Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle. On Geodesic Disks Enclosing Many Points. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.10,
  author =	{Bose, Prosenjit and Esteban, Guillermo and Orden, David and Silveira, Rodrigo I. and Tuttle, Tyler},
  title =	{{On Geodesic Disks Enclosing Many Points}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-242414},
  doi =		{10.4230/LIPIcs.WADS.2025.10},
  annote =	{Keywords: Enclosing disks, Geodesic disks, Bichromatic}
}
Artifact
Software
DOI: 10.4230/artifacts.23018
RolfSvenning/ContiguousArtGallery

Authors: Rolf Svenning

Abstract
Cite as

Rolf Svenning. RolfSvenning/ContiguousArtGallery (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{github_impl,
   title = {{RolfSvenning/ContiguousArtGallery}}, 
   author = {Svenning, Rolf},
   note = {Software, Independent Research Fund Denmark (DFF), grant 9131- 00113B, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7;origin=https://github.com/RolfSvenning/ContiguousArtGallery;visit=swh:1:snp:24512c962bdc05c9bff737a006e263acf6b13e78;anchor=swh:1:rev:af66971aa2b832e98dcd6b1fcf8eac88d5901b93}{\texttt{swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7}} (visited on 2025-06-20)},
   url = {https://github.com/RolfSvenning/ContiguousArtGallery},
   doi = {10.4230/artifacts.23018},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.26
Geometric Spanners of Bounded Tree-Width

Authors: Kevin Buchin, Carolin Rehs, and Torben Scheele

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

Abstract
Given a point set P in the Euclidean space, a geometric t-spanner G is a graph on P such that for every pair of points, the shortest path in G between those points is at most a factor t longer than the Euclidean distance between those points. The value t ≥ 1 is called the dilation of G. Commonly, the aim is to construct a t-spanner with additional desirable properties. In graph theory, a powerful tool to admit efficient algorithms is bounded tree-width. We therefore investigate the problem of computing geometric spanners with bounded tree-width and small dilation t. Let d be a fixed integer and P ⊂ ℝ^d be a point set with n points. We give a first algorithm to compute an 𝒪(n/k^{d/(d-1)})-spanner on P with tree-width at most k. The dilation obtained by the algorithm is asymptotically worst-case optimal for graphs with tree-width k: We show that there is a set of n points such that every spanner of tree-width k has dilation 𝒪(n/k^{d/(d-1)}). We further prove a tight dependency between tree-width and the number of edges in sparse connected planar graphs, which admits, for point sets in ℝ², a plane spanner with tree-width at most k and small maximum vertex degree. Finally, we show an almost tight bound on the minimum dilation of a spanning tree of n equally spaced points on a circle.
Cite as

Kevin Buchin, Carolin Rehs, and Torben Scheele. Geometric Spanners of Bounded Tree-Width. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.26,
  author =	{Buchin, Kevin and Rehs, Carolin and Scheele, Torben},
  title =	{{Geometric Spanners of Bounded Tree-Width}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-231786},
  doi =		{10.4230/LIPIcs.SoCG.2025.26},
  annote =	{Keywords: Computational Geometry, Geometric Spanner, Tree-width}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.20
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Authors: Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

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

Abstract
We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.
Cite as

Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.20,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas and Spalding-Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  title =	{{Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{20:1--20:21},
  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.20},
  URN =		{urn:nbn:de:0030-drops-231720},
  doi =		{10.4230/LIPIcs.SoCG.2025.20},
  annote =	{Keywords: Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.19
Polychromatic Coloring of Tuples in Hypergraphs

Authors: Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković

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

Abstract
A hypergraph H consists of a set V of vertices and a set E of hyperedges that are subsets of V. A t-tuple of H is a subset of t vertices of V. A t-tuple k-coloring of H is a mapping of its t-tuples into k colors. A coloring is called (t,k,f)-polychromatic if each hyperedge of E that has at least f vertices contains tuples of all the k colors. Let f_H(t,k) be the minimum f such that H has a (t,k,f)-polychromatic coloring. For a family of hypergraphs ℋ let f_H(t,k) be the maximum f_H(t,k) over all hypergraphs H in H. Determining f_H(t,k) has been an active research direction in recent years. This is challenging even for t = 1. We present several new results in this direction for t ≥ 2. - Let H be the family of hypergraphs H that is obtained by taking any set P of points in ℝ², setting V: = P and E: = {d ∩ P: d is a disk in ℝ²}. We prove that f_ H(2,k) ≤ 3.7^k, that is, the pairs of points (2-tuples) can be k-colored such that any disk containing at least 3.7^k points has pairs of all colors. We generalize this result to points and balls in higher dimensions. - For the family H of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that f_H(2,k) ≤ √{ck ln k} for some constant c. We then generalize this to higher dimensions, to other shapes, and to tuples of larger size. - For the family H of shrinkable hypergraphs of VC-dimension at most d we prove that f_ H(d+1,k) ≤ c^k for some constant c = c(d). Towards this bound, we obtain a result of independent interest: Every hypergraph with n vertices and with VC-dimension at most d has a (d+1)-tuple T of depth at least n/c, i.e., any hyperedge that contains T also contains n/c other vertices. - For the relationship between t-tuple coloring and vertex coloring in any hypergraph H we establish the inequality 1/e⋅ tk^{1/t} ≤ f_H(t,k) ≤ f_H(1,tk^{1/t}). For the special case of k = 2, referred to as the bichromatic coloring, we prove that t+1 ≤ f_H(t,2) ≤ max{f_H(1,2), t+1}; this improves upon the previous best known upper bound. - We study the relationship between tuple coloring and epsilon nets. In particular we show that if f_H(1,k) = O(k) for a hypergraph H with n vertices, then for any 0 < ε < 1 the t-tuples of H can be partitioned into Ω((εn/t)^t) ε-t-nets. This bound is tight when t is a constant.
Cite as

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković. Polychromatic Coloring of Tuples in Hypergraphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.19,
  author =	{Biniaz, Ahmad and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel and Smorodinsky, Shakhar and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Polychromatic Coloring of Tuples in Hypergraphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{19:1--19:17},
  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.19},
  URN =		{urn:nbn:de:0030-drops-231718},
  doi =		{10.4230/LIPIcs.SoCG.2025.19},
  annote =	{Keywords: Hypergraph Coloring, Polychromatic Coloring, Geometric Hypergraphs, Cover Decomposable Hypergraphs, Epsilon Nets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.17
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Authors: Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth

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

Abstract
We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}).
Cite as

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2025.17,
  author =	{Bhore, Sujoy and Chan, Timothy M. and Huang, Zhengcheng and Smorodinsky, Shakhar and T\'{o}th, Csaba D.},
  title =	{{Sparse Bounded Hop-Spanners for Geometric Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{17:1--17:15},
  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.17},
  URN =		{urn:nbn:de:0030-drops-231698},
  doi =		{10.4230/LIPIcs.SoCG.2025.17},
  annote =	{Keywords: Geometric Spanners, Geometric Intersection Graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.48
Exact Algorithms for Minimum Dilation Triangulation

Authors: Sándor P. Fekete, Phillip Keldenich, and Michael Perk

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

Abstract
We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set P of n points in the plane, find a triangulation T, such that a shortest Euclidean path in T between any pair of points increases by the smallest possible factor compared to their straight-line distance. No polynomial-time algorithm is known for the problem; moreover, evaluating the objective function involves computing the sum of (possibly many) square roots. On the other hand, the problem is not known to be NP-hard. (1) We provide practically robust methods and implementations for computing an MDT for benchmark sets with up to 30,000 points in reasonable time on commodity hardware, based on new geometric insights into the structure of optimal edge sets. Previous methods only achieved results for up to 200 points, so we extend the range of optimally solvable instances by a factor of 150. (2) We develop scalable techniques for accurately evaluating many shortest-path queries that arise as large-scale sums of square roots, allowing us to certify exact optimal solutions, with previous work relying on (possibly inaccurate) floating-point computations. (3) We resolve an open problem by establishing a lower bound of 1.44116 on the dilation of the regular 84-gon (and thus for arbitrary point sets), improving the previous worst-case lower bound of 1.4308 and greatly reducing the remaining gap to the upper bound of 1.4482 from the literature. In the process, we provide optimal solutions for regular n-gons up to n = 100.
Cite as

Sándor P. Fekete, Phillip Keldenich, and Michael Perk. Exact Algorithms for Minimum Dilation Triangulation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2025.48,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Perk, Michael},
  title =	{{Exact Algorithms for Minimum Dilation Triangulation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{48:1--48:18},
  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.48},
  URN =		{urn:nbn:de:0030-drops-232006},
  doi =		{10.4230/LIPIcs.SoCG.2025.48},
  annote =	{Keywords: dilation, minimum dilation triangulation, exact algorithms, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.51
Parameterized Geometric Graph Modification with Disk Scaling

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph G and an integer k ∈ ℕ as input, the goal is to determine whether we can perform at most k operations on G to transform it into a graph belonging to a specified graph class ℱ. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterized Geometric Graph Modification with Disk Scaling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.51},
  URN =		{urn:nbn:de:0030-drops-226795},
  doi =		{10.4230/LIPIcs.ITCS.2025.51},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.4
Minimum Plane Bichromatic Spanning Trees

Authors: Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case.
Cite as

Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth. Minimum Plane Bichromatic Spanning Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2024.4,
  author =	{A. Akitaya, Hugo and Biniaz, Ahmad and Demaine, Erik D. and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D.},
  title =	{{Minimum Plane Bichromatic Spanning Trees}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.4},
  URN =		{urn:nbn:de:0030-drops-221319},
  doi =		{10.4230/LIPIcs.ISAAC.2024.4},
  annote =	{Keywords: Bichromatic Spanning Tree, Minimum Spanning Tree, Plane Tree}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.36
Noncrossing Longest Paths and Cycles

Authors: Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.
Cite as

Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr. Noncrossing Longest Paths and Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aloupis_et_al:LIPIcs.GD.2024.36,
  author =	{Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Eppstein, David and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D. and Valtr, Pavel},
  title =	{{Noncrossing Longest Paths and Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.36},
  URN =		{urn:nbn:de:0030-drops-213203},
  doi =		{10.4230/LIPIcs.GD.2024.36},
  annote =	{Keywords: Longest Paths, Longest Cycles, Noncrossing Paths, Noncrossing Cycles}
}
  • Refine by Type
  • 27 Document/PDF
  • 12 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 13 2025
  • 3 2024
  • 1 2023
  • 2 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 19 Biniaz, Ahmad
  • 10 Bose, Prosenjit
  • 9 Maheshwari, Anil
  • 8 Smid, Michiel
  • 7 De Carufel, Jean-Lou
  • Show More...

  • Refine by Series/Journal
  • 27 LIPIcs

  • Refine by Classification
  • 19 Theory of computation → Computational geometry
  • 4 Theory of computation → Approximation algorithms analysis
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Mathematics of computing → Graph theory
  • 1 General and reference → Experimentation
  • Show More...

  • Refine by Keyword
  • 3 approximation algorithms
  • 2 Computational Geometry
  • 2 Geometric Spanners
  • 1 Approximation
  • 1 Art Gallery Problem
  • 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