95 Search Results for "Ahn, Hee-Kap"


Volume

LIPIcs, Volume 212

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

ISAAC 2021, December 6-8, 2021, Fukuoka, Japan

Editors: Hee-Kap Ahn and Kunihiko Sadakane

Document
Inscribing or Circumscribing a Histogon to a Convex Polygon

Authors: Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)


Abstract
We consider two optimization problems of approximating a convex polygon, one by a largest inscribed histogon and the other by a smallest circumscribed histogon. An axis-aligned histogon is an axis-aligned rectilinear polygon such that every horizontal edge has an integer length. A histogon of orientation θ is a copy of an axis-aligned histogon rotated by θ in counterclockwise direction. The goal is to find a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0,π). Depending on whether the horizontal width of a histogon is predetermined or not, we consider several different versions of the problem and present exact algorithms. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems.

Cite as

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Inscribing or Circumscribing a Histogon to a Convex Polygon. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.FSTTCS.2022.13,
  author =	{Chung, Jaehoon and Bae, Sang Won and Shin, Chan-Su and Yoon, Sang Duk and Ahn, Hee-Kap},
  title =	{{Inscribing or Circumscribing a Histogon to a Convex Polygon}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.13},
  URN =		{urn:nbn:de:0030-drops-174054},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.13},
  annote =	{Keywords: Shape simplification, Shape analysis, Histogon, Convex polygon}
}
Document
Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles

Authors: Mincheol Kim, Chanyang Seo, Taehoon Ahn, and Hee-Kap Ahn

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


Abstract
We present an algorithm to compute the geodesic L₁ farthest-point Voronoi diagram of m point sites in the presence of n rectangular obstacles in the plane. It takes O(nm+n log n + mlog m) construction time using O(nm) space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in O(log(n+m)) time.

Cite as

Mincheol Kim, Chanyang Seo, Taehoon Ahn, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.SoCG.2022.51,
  author =	{Kim, Mincheol and Seo, Chanyang and Ahn, Taehoon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{51:1--51:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.51},
  URN =		{urn:nbn:de:0030-drops-160596},
  doi =		{10.4230/LIPIcs.SoCG.2022.51},
  annote =	{Keywords: Geodesic distance, L₁ metric, farthest-point Voronoi diagram}
}
Document
Complete Volume
LIPIcs, Volume 212, ISAAC 2021, Complete Volume

Authors: Hee-Kap Ahn and Kunihiko Sadakane

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


Abstract
LIPIcs, Volume 212, ISAAC 2021, Complete Volume

Cite as

32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 1-1188, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@Proceedings{ahn_et_al:LIPIcs.ISAAC.2021,
  title =	{{LIPIcs, Volume 212, ISAAC 2021, Complete Volume}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{1--1188},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021},
  URN =		{urn:nbn:de:0030-drops-154329},
  doi =		{10.4230/LIPIcs.ISAAC.2021},
  annote =	{Keywords: LIPIcs, Volume 212, ISAAC 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Hee-Kap Ahn and Kunihiko Sadakane

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


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

Cite as

32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2021.0,
  author =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{0:i--0:xviii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.0},
  URN =		{urn:nbn:de:0030-drops-154330},
  doi =		{10.4230/LIPIcs.ISAAC.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Streaming Pattern Matching (Invited Talk)

Authors: Tatiana Starikovskaya

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


Abstract
Many classical algorithms for string processing assume that the input can be accessed in full via constant-time random access, which poses a serious limitation in the modern era of data deluge. In this talk, we will focus on the streaming model of computation that allows to overcome this issue. In this model of computation, we assume that the input arrives as a stream, one character at a time, which captures a situation when the data are sequential measurements or an output of an algorithm. The space complexity is defined as all the space used, including the space used to store any information about the input, which allows to develop ultra-efficient algorithms. The first streaming algorithm for pattern matching was presented in the seminal paper of Porat and Porat in FOCS 2009. For a pattern of length m, the algorithm uses only O(log m) space, while any classical algorithm requires Ω(m) space. This result served as a foundation of the area of streaming algorithms for pattern matching. After a brief survey of the area, we will discuss two questions in more details: the k-mismatch problem and the pattern matching with k-edits problem. In the k-mismatch problem, one is given a pattern and a text, and the task is to find all substrings of the text that have at most k mismatches with the pattern. The current best algorithm for this problem was given by Clifford, Kociumaka, and Porat in SODA 2019, and for a pattern of length m it uses O(k log m) space and Õ(√k) time per character of the text. In the pattern matching with k-edits problem, the task is similar, but one must find substrings that can be transformed into the pattern by at most k edits, i.e. substitutions, insertions, and deletions of a character. For this problem, the first streaming algorithm was presented by Kociumaka, Porat, and Starikovskaya in FOCS 2021. The algorithm takes Õ(poly(k)) space and Õ(poly(k)) time per character of the text.

Cite as

Tatiana Starikovskaya. Streaming Pattern Matching (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{starikovskaya:LIPIcs.ISAAC.2021.1,
  author =	{Starikovskaya, Tatiana},
  title =	{{Streaming Pattern Matching}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{1:1--1:1},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.1},
  URN =		{urn:nbn:de:0030-drops-154345},
  doi =		{10.4230/LIPIcs.ISAAC.2021.1},
  annote =	{Keywords: Streaming algorithms, Pattern matching, Hamming distance, Edit distance}
}
Document
Invited Talk
Spanning Properties of Variants of the Delaunay Graph (Invited Talk)

Authors: Prosenjit Bose

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


Abstract
A weighted geometric graph G is a graph whose n vertices are points in the plane and whose m edges are line segments weighted by the Euclidean distance between their endpoints. A t-spanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most t ≥ 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio or the stretch factor. Typically, G is a graph with Ω(n²) edges. As such, the goal in this area is to construct a subgraph G' that possesses several desirable properties such as O(n) edges and spanning ratio close to 1. In addition, when planarity is one of the desired properties, variants of Delaunay graphs play a vital role in the construction of planar geometric spanners. In this talk, we will provide a comprehensive overview of various results concerning the spanning ratio, among other several other properties, of different types of Delaunay graphs and their subgraphs.

Cite as

Prosenjit Bose. Spanning Properties of Variants of the Delaunay Graph (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bose:LIPIcs.ISAAC.2021.2,
  author =	{Bose, Prosenjit},
  title =	{{Spanning Properties of Variants of the Delaunay Graph}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{2:1--2:1},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.2},
  URN =		{urn:nbn:de:0030-drops-154352},
  doi =		{10.4230/LIPIcs.ISAAC.2021.2},
  annote =	{Keywords: Delaunay Graph, Geometric Graph, Graph Spanner}
}
Document
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

Authors: Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir

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


Abstract
We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.

Cite as

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3,
  author =	{Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha},
  title =	{{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{3:1--3: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3},
  URN =		{urn:nbn:de:0030-drops-154363},
  doi =		{10.4230/LIPIcs.ISAAC.2021.3},
  annote =	{Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions}
}
Document
Approximate Maximum Halfspace Discrepancy

Authors: Michael Matheny and Jeff M. Phillips

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


Abstract
Consider the geometric range space (X, H_d) where X ⊂ ℝ^d and H_d is the set of ranges defined by d-dimensional halfspaces. In this setting we consider that X is the disjoint union of a red and blue set. For each halfspace h ∈ H_d define a function Φ(h) that measures the "difference" between the fraction of red and fraction of blue points which fall in the range h. In this context the maximum discrepancy problem is to find the h^* = arg max_{h ∈ (X, H_d)} Φ(h). We aim to instead find an ĥ such that Φ(h^*) - Φ(ĥ) ≤ ε. This is the central problem in linear classification for machine learning, in spatial scan statistics for spatial anomaly detection, and shows up in many other areas. We provide a solution for this problem in O(|X| + (1/ε^d) log⁴ (1/ε)) time, for constant d, which improves polynomially over the previous best solutions. For d = 2 we show that this is nearly tight through conditional lower bounds. For different classes of Φ we can either provide a Ω(|X|^{3/2 - o(1)}) time lower bound for the exact solution with a reduction to APSP, or an Ω(|X| + 1/ε^{2-o(1)}) lower bound for the approximate solution with a reduction to 3Sum. A key technical result is a ε-approximate halfspace range counting data structure of size O(1/ε^d) with O(log (1/ε)) query time, which we can build in O(|X| + (1/ε^d) log⁴ (1/ε)) time.

Cite as

Michael Matheny and Jeff M. Phillips. Approximate Maximum Halfspace Discrepancy. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{matheny_et_al:LIPIcs.ISAAC.2021.4,
  author =	{Matheny, Michael and Phillips, Jeff M.},
  title =	{{Approximate Maximum Halfspace Discrepancy}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{4:1--4: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.4},
  URN =		{urn:nbn:de:0030-drops-154377},
  doi =		{10.4230/LIPIcs.ISAAC.2021.4},
  annote =	{Keywords: range spaces, halfspaces, scan statistics, fine-grained complexity}
}
Document
The VC-Dimension of Limited Visibility Terrains

Authors: Matt Gibson-Lopez and Zhongxiu Yang

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


Abstract
Visibility problems are fundamental to computational geometry, and many versions of geometric set cover where coverage is based on visibility have been considered. In most settings, points can see "infinitely far" so long as visibility is not "blocked" by some obstacle. In many applications, this may be an unreasonable assumption. In this paper, we consider a new model of visibility where no point can see any other point beyond a sight radius ρ. In particular, we consider this visibility model in the context of terrains. We show that the VC-dimension of limited visibility terrains is exactly 7. We give lower bound construction that shatters a set of 7 points, and we prove that shattering 8 points is not possible.

Cite as

Matt Gibson-Lopez and Zhongxiu Yang. The VC-Dimension of Limited Visibility Terrains. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{gibsonlopez_et_al:LIPIcs.ISAAC.2021.5,
  author =	{Gibson-Lopez, Matt and Yang, Zhongxiu},
  title =	{{The VC-Dimension of Limited Visibility Terrains}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{5:1--5:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.5},
  URN =		{urn:nbn:de:0030-drops-154386},
  doi =		{10.4230/LIPIcs.ISAAC.2021.5},
  annote =	{Keywords: VC-dimension, Terrain Guarding, Limited Visibility}
}
Document
Clustering with Neighborhoods

Authors: Hongyao Huang, Georgiy Klimenko, and Benjamin Raichel

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


Abstract
In the standard planar k-center clustering problem, one is given a set P of n points in the plane, and the goal is to select k center points, so as to minimize the maximum distance over points in P to their nearest center. Here we initiate the systematic study of the clustering with neighborhoods problem, which generalizes the k-center problem to allow the covered objects to be a set of general disjoint convex objects C rather than just a point set P. For this problem we first show that there is a PTAS for approximating the number of centers. Specifically, if r_opt is the optimal radius for k centers, then in n^O(1/ε²) time we can produce a set of (1+ε)k centers with radius ≤ r_opt. If instead one considers the standard goal of approximating the optimal clustering radius, while keeping k as a hard constraint, we show that the radius cannot be approximated within any factor in polynomial time unless P = NP, even when C is a set of line segments. When C is a set of unit disks we show the problem is hard to approximate within a factor of (√{13}-√3)(2-√3) ≈ 6.99. This hardness result complements our main result, where we show that when the objects are disks, of possibly differing radii, there is a (5+2√3)≈ 8.46 approximation algorithm. Additionally, for unit disks we give an O(n log k)+(k/ε)^O(k) time (1+ε)-approximation to the optimal radius, that is, an FPTAS for constant k whose running time depends only linearly on n. Finally, we show that the one dimensional version of the problem, even when intersections are allowed, can be solved exactly in O(n log n) time.

Cite as

Hongyao Huang, Georgiy Klimenko, and Benjamin Raichel. Clustering with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ISAAC.2021.6,
  author =	{Huang, Hongyao and Klimenko, Georgiy and Raichel, Benjamin},
  title =	{{Clustering with Neighborhoods}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{6:1--6:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.6},
  URN =		{urn:nbn:de:0030-drops-154398},
  doi =		{10.4230/LIPIcs.ISAAC.2021.6},
  annote =	{Keywords: Clustering, Approximation, Hardness}
}
Document
Approximating Longest Spanning Tree with Neighborhoods

Authors: Ahmad Biniaz

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


Abstract
We study the following maximization problem in the Euclidean plane: Given a collection of neighborhoods (polygonal regions) in the plane, the goal is to select a point in each neighborhood so that the longest spanning tree on selected points has maximum length. It is not known whether or not this problem is NP-hard. We present an approximation algorithm with ratio 0.548 for this problem. This improves the previous best known ratio of 0.511. The presented algorithm takes linear time after computing a diameter. Even though our algorithm itself is fairly simple, its analysis is rather involved. In some part we deal with a minimization problem with multiple variables. We use a sequence of geometric transformations to reduce the number of variables and simplify the analysis.

Cite as

Ahmad Biniaz. Approximating Longest Spanning Tree with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{biniaz:LIPIcs.ISAAC.2021.7,
  author =	{Biniaz, Ahmad},
  title =	{{Approximating Longest Spanning Tree with Neighborhoods}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.7},
  URN =		{urn:nbn:de:0030-drops-154401},
  doi =		{10.4230/LIPIcs.ISAAC.2021.7},
  annote =	{Keywords: Euclidean maximum spanning tree, spanning tree with neighborhoods, approximation algorithms}
}
Document
Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

Authors: Siu-Wing Cheng and Man Ting Wong

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


Abstract
We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The n input points are drawn from a hidden mixture of product distributions; we are only given an upper bound m = o(√n) on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of Ω(1/n). For any ε ∈ (0,1), after spending O(mn log^O(1)(mn) + m^ε n^(1+ε) log(mn)) time in a training phase, our algorithm achieves an O(1/ε n log m + 1/ε n 2^O(log^* n) + 1/ε H) expected running time with probability at least 1 - O(1/n), where H is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to O(1/ε n log m + 1/ε H).

Cite as

Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2021.8,
  author =	{Cheng, Siu-Wing and Wong, Man Ting},
  title =	{{Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{8:1--8:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.8},
  URN =		{urn:nbn:de:0030-drops-154418},
  doi =		{10.4230/LIPIcs.ISAAC.2021.8},
  annote =	{Keywords: entropy, Voronoi diagram, convex distance function, hidden mixture of product distributions}
}
Document
Connected Coordinated Motion Planning with Bounded Stretch

Authors: Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer

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


Abstract
We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is 𝒪(d), which is optimal up to constant factors.

Cite as

Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected Coordinated Motion Planning with Bounded Stretch. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2021.9,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Kosfeld, Ramin and Rieck, Christian and Scheffer, Christian},
  title =	{{Connected Coordinated Motion Planning with Bounded Stretch}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{9:1--9:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.9},
  URN =		{urn:nbn:de:0030-drops-154423},
  doi =		{10.4230/LIPIcs.ISAAC.2021.9},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}
Document
Enclosing Depth and Other Depth Measures

Authors: Patrick Schnider

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


Abstract
We study families of depth measures defined by natural sets of axioms. We show that any such depth measure is a constant factor approximation of Tukey depth. We further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy our most restrictive set of axioms, which includes Tukey depth. Along the way, we introduce and study a new depth measure called enclosing depth, which we believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.

Cite as

Patrick Schnider. Enclosing Depth and Other Depth Measures. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{schnider:LIPIcs.ISAAC.2021.10,
  author =	{Schnider, Patrick},
  title =	{{Enclosing Depth and Other Depth Measures}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{10:1--10: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.10},
  URN =		{urn:nbn:de:0030-drops-154431},
  doi =		{10.4230/LIPIcs.ISAAC.2021.10},
  annote =	{Keywords: Depth measures, Tukey depth, Tverberg theorem, Combinatorial Geometry}
}
  • Refine by Author
  • 19 Ahn, Hee-Kap
  • 15 Oh, Eunjin
  • 3 de Berg, Mark
  • 2 Bae, Sang Won
  • 2 Barba, Luis
  • Show More...

  • Refine by Classification
  • 25 Theory of computation → Computational geometry
  • 10 Theory of computation → Approximation algorithms analysis
  • 8 Theory of computation → Design and analysis of algorithms
  • 7 Mathematics of computing → Graph algorithms
  • 6 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 7 approximation algorithms
  • 4 Geodesic distance
  • 3 computational geometry
  • 3 facility location
  • 3 farthest-point Voronoi diagram
  • Show More...

  • Refine by Type
  • 94 document
  • 1 volume

  • Refine by Publication Year
  • 78 2021
  • 5 2017
  • 4 2016
  • 3 2018
  • 2 2022
  • 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