101 Search Results for "Cabello, Sergio"

Volume

LIPIcs, Volume 164

36th International Symposium on Computational Geometry (SoCG 2020)

SoCG 2020, June 23-26, 2020, Zürich, Switzerland

Editors: Sergio Cabello and Danny Z. Chen

Document
DOI: 10.4230/LIPIcs.SoCG.2024.4
Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane

Authors: Pankaj K. Agarwal, Esther Ezra, and Micha Sharir

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Let P be a set of m points in ℝ², let Σ be a set of n semi-algebraic sets of constant complexity in ℝ², let (S,+) be a semigroup, and let w: P → S be a weight function on the points of P. We describe a randomized algorithm for computing w(P∩σ) for every σ ∈ Σ in overall expected time O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n), where s > 0 is a constant that bounds the maximum complexity of the regions of Σ, and where the O^*(⋅) notation hides subpolynomial factors. For s ≥ 3, surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner. The latter takes O^*(m^{s/(2s-1)}n^{(2s-2)/(2s-1)} + m + n) time. Let Φ: Σ × P → {0,1} be the Boolean predicate (of constant complexity) such that Φ(σ,p) = 1 if p ∈ σ and 0 otherwise, and let Σ_Φ P = {(σ,p) ∈ Σ× P ∣ Φ(σ,p) = 1}. Our algorithm actually computes a partition ℬ_Φ of Σ_Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n). It is straightforward to compute w(P∩σ) for all σ ∈ Σ from ℬ_Φ. Similarly, if η: Σ → S is a weight function on the regions of Σ, ∑_{σ ∈ Σ: p ∈ σ} η(σ), for every point p ∈ P, can be computed from ℬ_Φ in a straightforward manner. We also mention a few other applications of computing ℬ_Φ.
Cite as

Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2024.4,
  author =	{Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha},
  title =	{{Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.4},
  URN =		{urn:nbn:de:0030-drops-199497},
  doi =		{10.4230/LIPIcs.SoCG.2024.4},
  annote =	{Keywords: Range-searching, semi-algebraic sets, pseudo-lines, duality, geometric cuttings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.31
Geometric Matching and Bottleneck Problems

Authors: Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Let P be a set of at most n points and let R be a set of at most n geometric ranges, such as disks and rectangles, where each p ∈ P has an associated supply s_{p} > 0, and each r ∈ R has an associated demand d_r > 0. A (many-to-many) matching is a set 𝒜 of ordered triples (p,r,a_{pr}) ∈ P × R × ℝ_{> 0} such that p ∈ r and the a_{pr}’s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing ∑_{(p,r,a_{pr}) ∈ 𝒜} a_{pr}. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of n red points P and a set of n blue points Q that minimizes the length of the longest edge. For the L_∞-metric, we can do this in time O(n^{1+ε}) in any fixed dimension, for the L₂-metric in the plane in time O(n^{4/3 + ε}), for any ε > 0.
Cite as

Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric Matching and Bottleneck Problems. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2024.31,
  author =	{Cabello, Sergio and Cheng, Siu-Wing and Cheong, Otfried and Knauer, Christian},
  title =	{{Geometric Matching and Bottleneck Problems}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31},
  URN =		{urn:nbn:de:0030-drops-199768},
  doi =		{10.4230/LIPIcs.SoCG.2024.31},
  annote =	{Keywords: Many-to-many matching, bipartite, planar, geometric, approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.41
GPU Algorithm for Enumerating PL Spheres of Picard Number 4: Application to Toric Topology

Authors: Suyoung Choi, Hyeontae Jang, and Mathieu Vallée

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The fundamental theorem for toric geometry states a toric manifold is encoded by a complete non-singular fan, whose combinatorial structure is the one of a PL sphere together with the set of generators of its rays. The wedge operation on a PL sphere increases its dimension without changing its Picard number. The seeds are the PL spheres that are not wedges. A PL sphere is toric colorable if it comes from a complete rational fan. A result of Choi and Park tells us that the set of toric seeds with a fixed Picard number p is finite. In fact, a toric PL sphere needs its facets to be bases of some binary matroids of corank p with neither coloops, nor cocircuits of size 2. We present and use a GPU-friendly and computationally efficient algorithm to enumerate this set of seeds, up to simplicial isomorphism. Explicitly, it allows us to obtain this set of seeds for Picard number 4 which is of main importance in toric topology for the characterization of toric manifolds with small Picard number. This follows the work of Kleinschmidt (1988) and Batyrev (1991) who fully classified toric manifolds with Picard number ≤ 3.
Cite as

Suyoung Choi, Hyeontae Jang, and Mathieu Vallée. GPU Algorithm for Enumerating PL Spheres of Picard Number 4: Application to Toric Topology. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{choi_et_al:LIPIcs.SoCG.2024.41,
  author =	{Choi, Suyoung and Jang, Hyeontae and Vall\'{e}e, Mathieu},
  title =	{{GPU Algorithm for Enumerating PL Spheres of Picard Number 4: Application to Toric Topology}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.41},
  URN =		{urn:nbn:de:0030-drops-199864},
  doi =		{10.4230/LIPIcs.SoCG.2024.41},
  annote =	{Keywords: PL sphere, simplicial sphere, toric manifold, Picard number, weak pseudo-manifold, characteristic map, binary matroid, parallel computing, GPU programming}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.1
Eliminating Crossings in Ordered Graphs

Authors: Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number. We show that the page number of an ordered graph with n vertices and m edges can be computed in 2^m ⋅ n^𝒪(1) time. An 𝒪(log n)-approximation of this number can be computed efficiently. We can decide in 2^𝒪(d √k log (d+k)) ⋅ n^𝒪(1) time whether it suffices to delete k edges of an ordered graph to obtain a d-planar layout (where every edge crosses at most d other edges) on one page. As an additional parameter, we consider the size h of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For h = 1, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number p. For h > 1, we give an XP algorithm with respect to h+p. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of t tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in 2ⁿ ⋅ n^𝒪(1) time either the number of crossings or, if we disallow crossings, the number of tracks.
Cite as

Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating Crossings in Ordered Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SWAT.2024.1,
  author =	{Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander},
  title =	{{Eliminating Crossings in Ordered Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1},
  URN =		{urn:nbn:de:0030-drops-200417},
  doi =		{10.4230/LIPIcs.SWAT.2024.1},
  annote =	{Keywords: Ordered graphs, book embedding, edge deletion, d-planar, hitting set}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.28
On k-Means for Segments and Polylines

Authors: Sergio Cabello and Panos Giannopoulos

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the problem of k-means clustering in the space of straight-line segments in ℝ² under the Hausdorff distance. For this problem, we give a (1+ε)-approximation algorithm that, for an input of n segments, for any fixed k, and with constant success probability, runs in time O(n + ε^{-O(k)} + ε^{-O(k)} ⋅ log^O(k) (ε^{-1})). The algorithm has two main ingredients. Firstly, we express the k-means objective in our metric space as a sum of algebraic functions and use the optimization technique of Vigneron [Antoine Vigneron, 2014] to approximate its minimum. Secondly, we reduce the input size by computing a small size coreset using the sensitivity-based sampling framework by Feldman and Langberg [Dan Feldman and Michael Langberg, 2011; Feldman et al., 2020]. Our results can be extended to polylines of constant complexity with a running time of O(n + ε^{-O(k)}).
Cite as

Sergio Cabello and Panos Giannopoulos. On k-Means for Segments and Polylines. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ESA.2023.28,
  author =	{Cabello, Sergio and Giannopoulos, Panos},
  title =	{{On k-Means for Segments and Polylines}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.28},
  URN =		{urn:nbn:de:0030-drops-186812},
  doi =		{10.4230/LIPIcs.ESA.2023.28},
  annote =	{Keywords: k-means clustering, segments, polylines, Hausdorff distance, Fr\'{e}chet mean}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.23
Long Plane Trees

Authors: Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In the longest plane spanning tree problem, we are given a finite planar point set 𝒫, and our task is to find a plane (i.e., noncrossing) spanning tree T_OPT for 𝒫 with maximum total Euclidean edge length |T_OPT|. Despite more than two decades of research, it remains open if this problem is NP-hard. Thus, previous efforts have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates |T_OPT|. The approximate trees in these algorithms all have small unweighted diameter, typically three or four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms. We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree T_ALG with diameter at most four and |T_ALG| ≥ 0.546 ⋅ |T_OPT|. This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter d ≥ 3, we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most d (compared to a longest plane tree without constraints).
Cite as

Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec. Long Plane Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2022.23,
  author =	{Cabello, Sergio and Hoffmann, Michael and Klost, Katharina and Mulzer, Wolfgang and Tkadlec, Josef},
  title =	{{Long Plane Trees}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.23},
  URN =		{urn:nbn:de:0030-drops-160311},
  doi =		{10.4230/LIPIcs.SoCG.2022.23},
  annote =	{Keywords: geometric network design, spanning trees, plane straight-line graphs, approximation algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2020.2
Some Open Problems in Computational Geometry (Invited Talk)

Authors: Sergio Cabello

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In this paper we shall encounter three open problems in Computational Geometry that are, in my opinion, interesting for a general audience interested in algorithms.
Cite as

Sergio Cabello. Some Open Problems in Computational Geometry (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 2:1-2:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cabello:LIPIcs.MFCS.2020.2,
  author =	{Cabello, Sergio},
  title =	{{Some Open Problems in Computational Geometry}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{2:1--2:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.2},
  URN =		{urn:nbn:de:0030-drops-126734},
  doi =		{10.4230/LIPIcs.MFCS.2020.2},
  annote =	{Keywords: barrier resilience, maximum matching, geometric graphs, fixed-parameter tractability, stochastic computational geometry}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2020
LIPIcs, Volume 164, SoCG 2020, Complete Volume

Authors: Sergio Cabello and Danny Z. Chen

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
LIPIcs, Volume 164, SoCG 2020, Complete Volume
Cite as

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1-1222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cabello_et_al:LIPIcs.SoCG.2020,
  title =	{{LIPIcs, Volume 164, SoCG 2020, Complete Volume}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1--1222},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020},
  URN =		{urn:nbn:de:0030-drops-121576},
  doi =		{10.4230/LIPIcs.SoCG.2020},
  annote =	{Keywords: LIPIcs, Volume 164, SoCG 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sergio Cabello and Danny Z. Chen

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2020.0,
  author =	{Cabello, Sergio and Chen, Danny Z.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.0},
  URN =		{urn:nbn:de:0030-drops-121587},
  doi =		{10.4230/LIPIcs.SoCG.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.1
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors: Eyal Ackerman, Balázs Keszegh, and Günter Rote

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.
Cite as

Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter},
  title =	{{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.1},
  URN =		{urn:nbn:de:0030-drops-121591},
  doi =		{10.4230/LIPIcs.SoCG.2020.1},
  annote =	{Keywords: Simple polygon, Ramsey theory, combinatorial geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.2
Dynamic Geometric Set Cover and Hitting Set

Authors: Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ¹ and ℝ². The first framework uses bootstrapping and gives a (1+ε)-approximate data structure for dynamic interval set cover in ℝ¹ with O(n^α/ε) amortized update time for any constant α > 0; in ℝ², this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n^(1/2+α)) amortized update time. The second framework uses local modification, and leads to a (1+ε)-approximate data structure for dynamic interval hitting set in ℝ¹ with Õ(1/ε) amortized update time; in ℝ², it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.
Cite as

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2020.2,
  author =	{Agarwal, Pankaj K. and Chang, Hsien-Chih and Suri, Subhash and Xiao, Allen and Xue, Jie},
  title =	{{Dynamic Geometric Set Cover and Hitting Set}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.2},
  URN =		{urn:nbn:de:0030-drops-121604},
  doi =		{10.4230/LIPIcs.SoCG.2020.2},
  annote =	{Keywords: Geometric set cover, Geometric hitting set, Dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.3
The Parameterized Complexity of Guarding Almost Convex Polygons

Authors: Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ℝ-complete [Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.
Cite as

Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SoCG.2020.3,
  author =	{Agrawal, Akanksha and Knudsen, Kristine V. K. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{The Parameterized Complexity of Guarding Almost Convex Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.3},
  URN =		{urn:nbn:de:0030-drops-121614},
  doi =		{10.4230/LIPIcs.SoCG.2020.3},
  annote =	{Keywords: Art Gallery, Reflex vertices, Monotone 2-CSP, Parameterized Complexity, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.4
Euclidean TSP in Narrow Strips

Authors: Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results. - For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).
Cite as

Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4,
  author =	{Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor},
  title =	{{Euclidean TSP in Narrow Strips}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.4},
  URN =		{urn:nbn:de:0030-drops-121628},
  doi =		{10.4230/LIPIcs.SoCG.2020.4},
  annote =	{Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.5
The ε-t-Net Problem

Authors: Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
  author =	{Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
  title =	{{The \epsilon-t-Net Problem}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5},
  URN =		{urn:nbn:de:0030-drops-121639},
  doi =		{10.4230/LIPIcs.SoCG.2020.5},
  annote =	{Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
  • Refine by Author
  • 13 Cabello, Sergio
  • 6 Fekete, Sándor P.
  • 4 Mulzer, Wolfgang
  • 4 Sharir, Micha
  • 3 Becker, Aaron T.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 Delaunay triangulation
  • 4 Topological Data Analysis
  • 4 approximation
  • 4 approximation algorithms
  • 3 Computational geometry
  • Show More...

  • Refine by Type
  • 100 document
  • 1 volume

  • Refine by Publication Year
  • 90 2020
  • 4 2024
  • 2 2017
  • 1 2015
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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