Search Results

Documents authored by Theocharous, Leonidas

Document
DOI: 10.4230/LIPIcs.SoCG.2024.2
Clustering with Few Disks to Minimize the Sum of Radii

Authors: Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous

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

Abstract
Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV '12]; however, the running time of this algorithm is 𝒪(n^881), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time 𝒪(n² log² n log² log n) was given over 30 years ago [Eppstein '92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected 𝒪(n log² n log² log n) time. We generalize this result to any constant dimension d, for which we give an 𝒪(n^{2-1/(⌈d/2⌉ + 1) + ε}) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected 𝒪(n² log² n log² log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution.
Cite as

Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous. Clustering with Few Disks to Minimize the Sum of Radii. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2024.2,
  author =	{Abrahamsen, Mikkel and de Berg, Sarita and Meijer, Lucas and Nusser, Andr\'{e} and Theocharous, Leonidas},
  title =	{{Clustering with Few Disks to Minimize the Sum of Radii}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-199472},
  doi =		{10.4230/LIPIcs.SoCG.2024.2},
  annote =	{Keywords: geometric clustering, minimize sum of radii, covering points with disks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.9
A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ²

Authors: Boris Aronov, Mark de Berg, and Leonidas Theocharous

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

Abstract
Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.
Cite as

Boris Aronov, Mark de Berg, and Leonidas Theocharous. A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ². In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.9,
  author =	{Aronov, Boris and de Berg, Mark and Theocharous, Leonidas},
  title =	{{A Clique-Based Separator for Intersection Graphs of Geodesic Disks in \mathbb{R}²}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-199540},
  doi =		{10.4230/LIPIcs.SoCG.2024.9},
  annote =	{Keywords: Computational geometry, intersection graphs, separator theorems}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.16
A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

Authors: Mark de Berg and Leonidas Theocharous

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

Abstract
Let 𝒫 be a simple polygon with m vertices and let P be a set of n points inside 𝒫. We prove that there exists, for any ε > 0, a set C ⊂ P of size O(1/ε²) such that the following holds: for any query point q inside the polygon 𝒫, the geodesic distance from q to its furthest neighbor in C is at least 1-ε times the geodesic distance to its further neighbor in P. Thus the set C can be used for answering ε-approximate furthest-neighbor queries with a data structure whose storage requirement is independent of the size of P. The coreset can be constructed in O(1/(ε) (nlog(1/ε) + (n+m)log(n+m))) time.
Cite as

Mark de Berg and Leonidas Theocharous. A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2024.16,
  author =	{de Berg, Mark and Theocharous, Leonidas},
  title =	{{A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{16:1--16:16},
  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.16},
  URN =		{urn:nbn:de:0030-drops-199613},
  doi =		{10.4230/LIPIcs.SoCG.2024.16},
  annote =	{Keywords: Furthest-neighbor queries, polygons, geodesic distance, coreset}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.23
Clustering in Polygonal Domains

Authors: Mark de Berg, Leyla Biabani, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We study various clustering problems for a set D of n points in a polygonal domain P under the geodesic distance. We start by studying the discrete k-median problem for D in P. We develop an exact algorithm which runs in time poly(n,m) + n^O(√k), where m is the complexity of the domain. Subsequently, we show that our approach can also be applied to solve the k-center problem with z outliers in the same running time. Next, we turn our attention to approximation algorithms. In particular, we study the k-center problem in a simple polygon and show how to obtain a (1+ε)-approximation algorithm which runs in time 2^{O((k log(k))/ε)} (n log(m) + m). To obtain this, we demonstrate that a previous approach by Bădoiu et al. [Bâdoiu et al., 2002; Bâdoiu and Clarkson, 2003] that works in ℝ^d, carries over to the setting of simple polygons. Finally, we study the 1-center problem in a simple polygon in the presence of z outliers. We show that a coreset C of size O(z) exists, such that the 1-center of C is a 3-approximation of the 1-center of D, when z outliers are allowed. This result is actually more general and carries over to any metric space, which to the best of our knowledge was not known so far. By extending this approach, we show that for the 1-center problem under the Euclidean metric in ℝ², there exists an ε-coreset of size O(z/ε).
Cite as

Mark de Berg, Leyla Biabani, Morteza Monemizadeh, and Leonidas Theocharous. Clustering in Polygonal Domains. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2023.23,
  author =	{de Berg, Mark and Biabani, Leyla and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{Clustering in Polygonal Domains}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.23},
  URN =		{urn:nbn:de:0030-drops-193252},
  doi =		{10.4230/LIPIcs.ISAAC.2023.23},
  annote =	{Keywords: clustering, geodesic distance, coreset, outliers}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.5
TSP in a Simple Polygon

Authors: Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2^O(√nlog n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.
Cite as

Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous. TSP in a Simple Polygon. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.ESA.2022.5,
  author =	{Alkema, Henk and de Berg, Mark and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{TSP in a Simple Polygon}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.5},
  URN =		{urn:nbn:de:0030-drops-169434},
  doi =		{10.4230/LIPIcs.ESA.2022.5},
  annote =	{Keywords: Traveling Salesman Problem, Subexponential algorithms, TSP with obstacles}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.22
Clique-Based Separators for Geometric Intersection Graphs

Authors: Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Let F be a set of n objects in the plane and let 𝒢^{×}(F) be its intersection graph. A balanced clique-based separator of 𝒢^{×}(F) is a set 𝒮 consisting of cliques whose removal partitions 𝒢^{×}(F) into components of size at most δ n, for some fixed constant δ < 1. The weight of a clique-based separator is defined as ∑_{C ∈ 𝒮}log (|C|+1). Recently De Berg et al. (SICOMP 2020) proved that if S consists of convex fat objects, then 𝒢^{×}(F) admits a balanced clique-based separator of weight O(√n). We extend this result in several directions, obtaining the following results. - Map graphs admit a balanced clique-based separator of weight O(√n), which is tight in the worst case. - Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n^{2/3} log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(√n log n). - Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n^{2/3} log n). - Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(√n + r log(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for q-Coloring for constant q in these graph classes.
Cite as

Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous. Clique-Based Separators for Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.22,
  author =	{de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{Clique-Based Separators for Geometric Intersection Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{22:1--22:15},
  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.22},
  URN =		{urn:nbn:de:0030-drops-154556},
  doi =		{10.4230/LIPIcs.ISAAC.2021.22},
  annote =	{Keywords: Computational geometry, intersection graphs, separator theorems}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact