19 Search Results for "Oh, Eunjin"

Document
DOI: 10.4230/LIPIcs.ESA.2023.85
Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs

Authors: Eunjin Oh and Seunghyeok Oh

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

Abstract
In this paper, we study the maximum clique problem on hyperbolic random graphs. A hyperbolic random graph is a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. We propose a simple algorithm for finding a maximum clique in hyperbolic random graph. We first analyze the running time of our algorithm theoretically. We can compute a maximum clique on a hyperbolic random graph G in O(m + n^{4.5(1-α)}) expected time if a geometric representation is given or in O(m + n^{6(1-α)}) expected time if a geometric representation is not given, where n and m denote the numbers of vertices and edges of G, respectively, and α denotes a parameter controlling the power-law exponent of the degree distribution of G. Also, we implemented and evaluated our algorithm empirically. Our algorithm outperforms the previous algorithm [BFK18] practically and theoretically. Beyond the hyperbolic random graphs, we have experiment on real-world networks. For most of instances, we get large cliques close to the optimum solutions efficiently.
Cite as

Eunjin Oh and Seunghyeok Oh. Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 85:1-85:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ESA.2023.85,
  author =	{Oh, Eunjin and Oh, Seunghyeok},
  title =	{{Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{85:1--85:15},
  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.85},
  URN =		{urn:nbn:de:0030-drops-187384},
  doi =		{10.4230/LIPIcs.ESA.2023.85},
  annote =	{Keywords: Maximum cliques, hyperbolic random graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.46
Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces

Authors: Kyungjin Cho and Eunjin Oh

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

Abstract
In this paper, we present a linear-time approximation scheme for k-means clustering of incomplete data points in d-dimensional Euclidean space. An incomplete data point with Δ > 0 unspecified entries is represented as an axis-parallel affine subspace of dimension Δ. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k-means clustering of axis-parallel affine subspaces of dimension Δ that yields an (1+ε)-approximate solution in O(nd) time. The constants hidden behind O(⋅) depend only on Δ, ε and k. This improves the O(n² d)-time algorithm by Eiben et al. [SODA'21] by a factor of n.
Cite as

Kyungjin Cho and Eunjin Oh. Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 46:1-46:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.ISAAC.2021.46,
  author =	{Cho, Kyungjin and Oh, Eunjin},
  title =	{{Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{46:1--46: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.46},
  URN =		{urn:nbn:de:0030-drops-154794},
  doi =		{10.4230/LIPIcs.ISAAC.2021.46},
  annote =	{Keywords: k-means clustering, affine subspaces}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.47
Feedback Vertex Set on Geometric Intersection Graphs

Authors: Shinwoo An and Eunjin Oh

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

Abstract
In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time 2^O(√k)(n+m), where n and m denote the numbers of vertices and edges, respectively. This improves the 2^O(√klog k) n^O(1)-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.
Cite as

Shinwoo An and Eunjin Oh. Feedback Vertex Set on Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 47:1-47:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2021.47,
  author =	{An, Shinwoo and Oh, Eunjin},
  title =	{{Feedback Vertex Set on Geometric Intersection Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{47:1--47:12},
  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.47},
  URN =		{urn:nbn:de:0030-drops-154807},
  doi =		{10.4230/LIPIcs.ISAAC.2021.47},
  annote =	{Keywords: Feedback vertex set, intersection graphs, parameterized algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.52
Shortest-Path Queries in Geometric Networks

Authors: Eunjin Oh

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
A Euclidean t-spanner for a point set V ⊂ ℝ^d is a graph such that, for any two points p and q in V, the distance between p and q in the graph is at most t times the Euclidean distance between p and q. Gudmundsson et al. [TALG 2008] presented a data structure for answering ε-approximate distance queries in a Euclidean spanner in constant time, but it seems unlikely that one can report the path itself using this data structure. In this paper, we present a data structure of size O(nlog n) that answers ε-approximate shortest-path queries in time linear in the size of the output.
Cite as

Eunjin Oh. Shortest-Path Queries in Geometric Networks. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 52:1-52:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oh:LIPIcs.ISAAC.2020.52,
  author =	{Oh, Eunjin},
  title =	{{Shortest-Path Queries in Geometric Networks}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.52},
  URN =		{urn:nbn:de:0030-drops-133963},
  doi =		{10.4230/LIPIcs.ISAAC.2020.52},
  annote =	{Keywords: Shortest path, Euclidean spanner, data structure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.51
Point Location in Incremental Planar Subdivisions

Authors: Eunjin Oh

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specifically, we present an O(n log n)-space data structure for this problem that supports queries in O(log^2 n) time and updates in O(log n log log n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental planar subdivisions. Its update time is significantly faster than the update time of the best known data structure for fully-dynamic (possibly disconnected) planar subdivisions.
Cite as

Eunjin Oh. Point Location in Incremental Planar Subdivisions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{oh:LIPIcs.ISAAC.2018.51,
  author =	{Oh, Eunjin},
  title =	{{Point Location in Incremental Planar Subdivisions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.51},
  URN =		{urn:nbn:de:0030-drops-99991},
  doi =		{10.4230/LIPIcs.ISAAC.2018.51},
  annote =	{Keywords: Dynamic point location, general incremental planar subdivisions}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.59
Minimizing Distance-to-Sight in Polygonal Domains

Authors: Eunjin Oh

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper, we consider the quickest pair-visibility problem in polygonal domains. Given two points in a polygonal domain with h holes of total complexity n, we want to minimize the maximum distance that the two points travel in order to see each other in the polygonal domain. We present an O(n log^2 n+h^2 log^4 h)-time algorithm for this problem. We show that this running time is almost optimal unless the 3sum problem can be solved in O(n^{2-epsilon}) time for some epsilon>0.
Cite as

Eunjin Oh. Minimizing Distance-to-Sight in Polygonal Domains. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 59:1-59:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{oh:LIPIcs.ISAAC.2018.59,
  author =	{Oh, Eunjin},
  title =	{{Minimizing Distance-to-Sight in Polygonal Domains}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.59},
  URN =		{urn:nbn:de:0030-drops-100073},
  doi =		{10.4230/LIPIcs.ISAAC.2018.59},
  annote =	{Keywords: Visibility in polygonal domains, shortest path in polygonal domains}
}
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}
}
  • Refine by Author
  • 19 Oh, Eunjin
  • 12 Ahn, Hee-Kap
  • 2 Barba, Luis
  • 2 Korman, Matias
  • 1 Ahn, Hee Kap
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 3 Geodesic distance
  • 3 facility location
  • 3 simple polygons
  • 2 farthest-point Voronoi diagram
  • 1 1-center problem
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 5 2017
  • 5 2018
  • 4 2016
  • 2 2021
  • 1 2015
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact