Search Results

Documents authored by Ahn, Hee-Kap

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.13
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.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
DOI: 10.4230/LIPIcs.SoCG.2022.51
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.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
DOI: 10.4230/LIPIcs.ISAAC.2021
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.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
DOI: 10.4230/LIPIcs.ISAAC.2021.0
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.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
DOI: 10.4230/LIPIcs.FSTTCS.2021.19
Largest Similar Copies of Convex Polygons in Polygonal Domains

Authors: Taekang Eom, Seungjun Lee, and Hee-Kap Ahn

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Given a convex polygon with k vertices and a polygonal domain consisting of polygonal obstacles with n vertices in total in the plane, we study the optimization problem of finding a largest similar copy of the polygon that can be placed in the polygonal domain without intersecting the obstacles. We present an upper bound O(k²n²λ₄(k)) on the number of combinatorial changes occurred to the underlying structure during the rotation of the polygon, together with an O(k²n²λ₄(k)log n)-time deterministic algorithm for the problem. This improves upon the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 27 years. Our result also improves the time complexity of the high-clearance motion planning algorithm by Chew and Kedem.
Cite as

Taekang Eom, Seungjun Lee, and Hee-Kap Ahn. Largest Similar Copies of Convex Polygons in Polygonal Domains. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{eom_et_al:LIPIcs.FSTTCS.2021.19,
  author =	{Eom, Taekang and Lee, Seungjun and Ahn, Hee-Kap},
  title =	{{Largest Similar Copies of Convex Polygons in Polygonal Domains}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.19},
  URN =		{urn:nbn:de:0030-drops-155300},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.19},
  annote =	{Keywords: Polygon placement, Largest similar copy, Polygonal domain}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.12
Maximum-Area Rectangles in a Simple Polygon

Authors: Yujin Choi, Seungjun Lee, and Hee-Kap Ahn

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
We study the problem of finding maximum-area rectangles contained in a polygon in the plane. There has been a fair amount of work for this problem when the rectangles have to be axis-aligned or when the polygon is convex. We consider this problem in a simple polygon with n vertices, possibly with holes, and with no restriction on the orientation of the rectangles. We present an algorithm that computes a maximum-area rectangle in O(n^3 log n) time using O(kn^2) space, where k is the number of reflex vertices of P. Our algorithm can report all maximum-area rectangles in the same time using O(n^3) space. We also present a simple algorithm that finds a maximum-area rectangle contained in a convex polygon with n vertices in O(n^3) time using O(n) space.
Cite as

Yujin Choi, Seungjun Lee, and Hee-Kap Ahn. Maximum-Area Rectangles in a Simple Polygon. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{choi_et_al:LIPIcs.FSTTCS.2019.12,
  author =	{Choi, Yujin and Lee, Seungjun and Ahn, Hee-Kap},
  title =	{{Maximum-Area Rectangles in a Simple Polygon}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.12},
  URN =		{urn:nbn:de:0030-drops-115745},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.12},
  annote =	{Keywords: Maximum-area rectangle, largest rectangle, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.62
Approximate Range Queries for Clustering

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study the approximate range searching for three variants of the clustering problem with a set P of n points in d-dimensional Euclidean space and axis-parallel rectangular range queries: the k-median, k-means, and k-center range-clustering query problems. We present data structures and query algorithms that compute (1+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0.
Cite as

Eunjin Oh and Hee-Kap Ahn. Approximate Range Queries for Clustering. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SoCG.2018.62,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Approximate Range Queries for Clustering}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.62},
  URN =		{urn:nbn:de:0030-drops-87755},
  doi =		{10.4230/LIPIcs.SoCG.2018.62},
  annote =	{Keywords: Approximate clustering, orthogonal range queries}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.63
Point Location in Dynamic Planar Subdivisions

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.
Cite as

Eunjin Oh and Hee-Kap Ahn. Point Location in Dynamic Planar Subdivisions. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SoCG.2018.63,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Point Location in Dynamic Planar Subdivisions}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.63},
  URN =		{urn:nbn:de:0030-drops-87769},
  doi =		{10.4230/LIPIcs.SoCG.2018.63},
  annote =	{Keywords: dynamic point location, general subdivision}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.6
On Romeo and Juliet Problems: Minimizing Distance-to-Sight

Authors: Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn, and Darren Strash

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance these persons travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log^2 n) time for any two query positions where the two persons lie.
Cite as

Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn, and Darren Strash. On Romeo and Juliet Problems: Minimizing Distance-to-Sight. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.SWAT.2018.6,
  author =	{Ahn, Hee-Kap and Oh, Eunjin and Schlipf, Lena and Stehn, Fabian and Strash, Darren},
  title =	{{On Romeo and Juliet Problems: Minimizing Distance-to-Sight}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.6},
  URN =		{urn:nbn:de:0030-drops-88322},
  doi =		{10.4230/LIPIcs.SWAT.2018.6},
  annote =	{Keywords: Visibility polygon, shortest-path, watchman problems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.3
Faster Algorithms for Growing Prioritized Disks and Rectangles

Authors: Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and Antoine Vigneron

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.
Cite as

Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and Antoine Vigneron. Faster Algorithms for Growing Prioritized Disks and Rectangles. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2017.3,
  author =	{Ahn, Hee-Kap and Bae, Sang Won and Choi, Jongmin and Korman, Matias and Mulzer, Wolfgang and Oh, Eunjin and Park, Ji-won and van Renssen, Andr\'{e} and Vigneron, Antoine},
  title =	{{Faster Algorithms for Growing Prioritized Disks and Rectangles}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.3},
  URN =		{urn:nbn:de:0030-drops-82199},
  doi =		{10.4230/LIPIcs.ISAAC.2017.3},
  annote =	{Keywords: map labeling, growing disks, elimination order}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.60
Finding Pairwise Intersections of Rectangles in a Query Rectangle

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We consider the following problem: Preprocess a set S of n axis-parallel boxes in \mathbb{R}^d so that given a query of an axis-parallel box Q in \mathbb{R}^d, the pairs of boxes of S whose intersection intersects the query box can be reported efficiently. For the case that d=2, we present a data structure of size O(n\log n) supporting O(\log n+k) query time, where k is the size of the output. This improves the previously best known result by de Berg et al. which requires O(\log n\log^* n+ k\log n) query time using O(n\log n) space.There has been no known result for this problem for higher dimensions, except that for d=3, the best known data structure supports O(\sqrt{n}+k\log^2\log^* n) query time using O(n\sqrt {n}\log n) space. For a constant d>2, we present a data structure supporting O(n^{1-\delta}\log^{d-1} n + k \polylog n) query time for any constant 1/d\leq\delta<1.The size of the data structure is O(n^{\delta d}\log n) if 1/d\leq\delta<1/2, or O(n^{\delta d-2\delta+1}) if 1/2\leq \delta<1.
Cite as

Eunjin Oh and Hee-Kap Ahn. Finding Pairwise Intersections of Rectangles in a Query Rectangle. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 60:1-60:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ISAAC.2017.60,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Finding Pairwise Intersections of Rectangles in a Query Rectangle}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{60:1--60:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.60},
  URN =		{urn:nbn:de:0030-drops-82417},
  doi =		{10.4230/LIPIcs.ISAAC.2017.60},
  annote =	{Keywords: Geometric data structures, axis-parallel rectangles, intersection}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.61
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We are given a read-only memory for input and a write-only stream for output. For a positive integer parameter s, an s-workspace algorithm is an algorithm using only O(s) words of workspace in addition to the memory for input. In this paper, we present an O(n^2/s)-time s-workspace algorithm for subdividing a simple polygon into O(\min\{n/s,s\}) subpolygons of complexity O(\max\{n/s,s\}). As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately: (1) computing the shortest path between two points inside a simple n-gon, (2) computing the shortest path tree from a point inside a simple n-gon, (3) computing a triangulation of a simple n-gon. In addition, we improve the algorithm for the second problem even further.
Cite as

Eunjin Oh and Hee-Kap Ahn. A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ISAAC.2017.61,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.61},
  URN =		{urn:nbn:de:0030-drops-82401},
  doi =		{10.4230/LIPIcs.ISAAC.2017.61},
  annote =	{Keywords: Time-space trade-off, simple polygon, shortest path, shortest path tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.51
Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We consider the geodesic convex hulls of points in a simple polygonal region in the presence of non-crossing line segments (barriers) that subdivide the region into simply connected faces. We present an algorithm together with data structures for maintaining the geodesic convex hull of points in each face in a sublinear update time under the fully-dynamic setting where both input points and barriers change by insertions and deletions. The algorithm processes a mixed update sequence of insertions and deletions of points and barriers. Each update takes O(n^2/3 log^2 n) time with high probability, where n is the total number of the points and barriers at the moment. Our data structures support basic queries on the geodesic convex hull, each of which takes O(polylog n) time. In addition, we present an algorithm together with data structures for geodesic triangle counting queries under the fully-dynamic setting. With high probability, each update takes O(n^2/3 log n) time, and each query takes O(n^2/3 log n) time.
Cite as

Eunjin Oh and Hee-Kap Ahn. Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SoCG.2017.51,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.51},
  URN =		{urn:nbn:de:0030-drops-72198},
  doi =		{10.4230/LIPIcs.SoCG.2017.51},
  annote =	{Keywords: Dynamic geodesic convex hull, dynamic simple polygons}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.52
Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Given a set of sites in a simple polygon, a geodesic Voronoi diagram partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m < n/polylog n. Moreover, the algorithms for the nearest-point and farthest-point Voronoi diagrams are optimal for m < n/polylog n. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.
Cite as

Eunjin Oh and Hee-Kap Ahn. Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SoCG.2017.52,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.52},
  URN =		{urn:nbn:de:0030-drops-72184},
  doi =		{10.4230/LIPIcs.SoCG.2017.52},
  annote =	{Keywords: Simple polygons, Voronoi diagrams, geodesic distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.58
Assigning Weights to Minimize the Covering Radius in the Plane

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Given a set P of n points in the plane and a multiset W of k weights with k leq n, we assign a weight in W to a point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we give two algorithms which take O(k^2 n^2 log^4 n) time and O(k^5 n log^4 k + kn log^3 n) time, respectively. For a constant k, the second algorithm takes only O(n log^3 n) time, which is near-linear.
Cite as

Eunjin Oh and Hee-Kap Ahn. Assigning Weights to Minimize the Covering Radius in the Plane. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 58:1-58:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ISAAC.2016.58,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{Assigning Weights to Minimize the Covering Radius in the Plane}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{58:1--58:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.58},
  URN =		{urn:nbn:de:0030-drops-68275},
  doi =		{10.4230/LIPIcs.ISAAC.2016.58},
  annote =	{Keywords: Weighted center, facility location, weight assignment, combinatorial op- timization, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.59
A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree

Authors: Eunjin Oh and Hee-Kap Ahn

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We consider the problem of finding a shortcut connecting two vertices of a graph that minimizes the diameter of the resulting graph. We present an O(n^2 log^3 n)-time algorithm using linear space for the case that the input graph is a tree consisting of n vertices. Additionally, we present an O(n^2 log^3 n)-time algorithm using linear space for a continuous version of this problem.
Cite as

Eunjin Oh and Hee-Kap Ahn. A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ISAAC.2016.59,
  author =	{Oh, Eunjin and Ahn, Hee-Kap},
  title =	{{A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.59},
  URN =		{urn:nbn:de:0030-drops-68283},
  doi =		{10.4230/LIPIcs.ISAAC.2016.59},
  annote =	{Keywords: Network Augmentation, Shortcuts, Diameter, Trees}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.29
Constrained Geodesic Centers of a Simple Polygon

Authors: Eunjin Oh, Wanbin Son, and Hee-Kap Ahn

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
For any two points in a simple polygon P, the geodesic distance between them is the length of the shortest path contained in P that connects them. A geodesic center of a set S of sites (points) with respect to P is a point in P that minimizes the geodesic distance to its farthest site. In many realistic facility location problems, however, the facilities are constrained to lie in feasible regions. In this paper, we show how to compute the geodesic centers constrained to a set of line segments or simple polygonal regions contained in P. Our results provide substantial improvements over previous algorithms.
Cite as

Eunjin Oh, Wanbin Son, and Hee-Kap Ahn. Constrained Geodesic Centers of a Simple Polygon. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SWAT.2016.29,
  author =	{Oh, Eunjin and Son, Wanbin and Ahn, Hee-Kap},
  title =	{{Constrained Geodesic Centers of a Simple Polygon}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.29},
  URN =		{urn:nbn:de:0030-drops-60516},
  doi =		{10.4230/LIPIcs.SWAT.2016.29},
  annote =	{Keywords: Geodesic distance, simple polygons, constrained center, facility location, farthest-point Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.56
The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon

Authors: Eunjin Oh, Luis Barba, and Hee-Kap Ahn

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.
Cite as

Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SoCG.2016.56,
  author =	{Oh, Eunjin and Barba, Luis and Ahn, Hee-Kap},
  title =	{{The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.56},
  URN =		{urn:nbn:de:0030-drops-59481},
  doi =		{10.4230/LIPIcs.SoCG.2016.56},
  annote =	{Keywords: Geodesic distance, simple polygons, farthest-point Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.498
Overlap of Convex Polytopes under Rigid Motion

Authors: Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We present an algorithm to compute an approximate overlap of two convex polytopes P_1 and P_2 in R^3 under rigid motion. Given any epsilon in (0,1/2], our algorithm runs in O(epsilon^{-3}n log^{3.5}n) time with probability 1 - n^{-O(1)} and returns a (1-epsilon)-approximate maximum overlap, provided that the maximum overlap is at least lambda max(|P_1|,|P_2|) for some given constant lambda in (0,1].
Cite as

Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon. Overlap of Convex Polytopes under Rigid Motion. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 498-509, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.FSTTCS.2012.498,
  author =	{Ahn, Hee-Kap and Cheng, Siu-Wing and Kweon, Hyuk Jun and Yon, Juyoung},
  title =	{{Overlap of Convex Polytopes under Rigid Motion}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{498--509},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.498},
  URN =		{urn:nbn:de:0030-drops-38845},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.498},
  annote =	{Keywords: convex polytope, overlap, approximation, rigid motion}
}
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact