Search Results

Documents authored by Wang, Haitao

Document
DOI: 10.4230/LIPIcs.MFCS.2024.68
Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems

Authors: Gang Liu and Haitao Wang

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set P of n points and a set S of m disks in the plane, the disk hitting set problem asks for a smallest subset of P such that every disk of S contains at least one point in the subset. The problem is NP-hard. This paper considers a line-constrained version in which all disks have their centers on a line. We present an O(mlog²n+(n+m)log(n+m)) time algorithm for the problem. This improves the previous result of O(m²log m+(n+m)log(n+m)) time for the weighted case of the problem where every point of P has a weight and the objective is to minimize the total weight of the hitting set. Our algorithm also solves a more general line-separable problem with a single intersection property: The points of P and the disk centers are separated by a line 𝓁 and the boundary of every two disks intersect at most once on the side of 𝓁 containing P.
Cite as

Gang Liu and Haitao Wang. Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.68,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.68},
  URN =		{urn:nbn:de:0030-drops-206240},
  doi =		{10.4230/LIPIcs.MFCS.2024.68},
  annote =	{Keywords: hitting set, line-constrained, line-separable, unit disks, half-planes, coverage}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.70
On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Authors: Gang Liu and Haitao Wang

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set P of n points and a set S of n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an O(n^{3/2}log² n) time algorithm for the problem. This improves the previously best work of O(n²log n) time. Our result leads to an algorithm of O(n^{7/2}log² n) time for the halfplane coverage problem (i.e., using n weighted halfplanes to cover n points), an improvement over the previous O(n⁴log n) time solution. If all halfplanes are lower ones, our algorithm runs in O(n^{3/2}log² n) time, while the previous best algorithm takes O(n²log n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities.
Cite as

Gang Liu and Haitao Wang. On Line-Separable Weighted Unit-Disk Coverage and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.70,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{On Line-Separable Weighted Unit-Disk Coverage and Related Problems}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.70},
  URN =		{urn:nbn:de:0030-drops-206265},
  doi =		{10.4230/LIPIcs.MFCS.2024.70},
  annote =	{Keywords: Line-separable, unit disks, halfplanes, geometric coverage, geometric hitting set}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.24
Dynamic Convex Hulls for Simple Paths

Authors: Bruce Brewer, Gerth Stølting Brodal, and Haitao Wang

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

Abstract
We consider two restricted cases of the planar dynamic convex hull problem with point insertions and deletions. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case, which is more general, assumes that the points in the deque constitute a simple path. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(log n) time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+log n) time, where h is the number of edges of the convex hull. For the 1-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(log h) time. All our time bounds are worst case. In addition, we prove lower bounds that match these time bounds, and thus our results are optimal.
Cite as

Bruce Brewer, Gerth Stølting Brodal, and Haitao Wang. Dynamic Convex Hulls for Simple Paths. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.SoCG.2024.24,
  author =	{Brewer, Bruce and Brodal, Gerth St{\o}lting and Wang, Haitao},
  title =	{{Dynamic Convex Hulls for Simple Paths}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.24},
  URN =		{urn:nbn:de:0030-drops-199699},
  doi =		{10.4230/LIPIcs.SoCG.2024.24},
  annote =	{Keywords: Dynamic convex hull, convex hull queries, simple paths, path updates, deque}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.40
Optimal Algorithm for the Planar Two-Center Problem

Authors: Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue

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

Abstract
We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set S of n points in the plane and the goal is to find two smallest congruent disks whose union contains all points of S. A longstanding open problem has been to obtain an O(nlog n)-time algorithm for planar two-center, matching the Ω(nlog n) lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in O(nlog² n) time. In this paper, we present an O(nlog n)-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
Cite as

Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue. Optimal Algorithm for the Planar Two-Center Problem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.SoCG.2024.40,
  author =	{Cho, Kyungjin and Oh, Eunjin and Wang, Haitao and Xue, Jie},
  title =	{{Optimal Algorithm for the Planar Two-Center Problem}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.40},
  URN =		{urn:nbn:de:0030-drops-199857},
  doi =		{10.4230/LIPIcs.SoCG.2024.40},
  annote =	{Keywords: two-center, r-coverage, disk coverage, circular hulls}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.79
Algorithms for Halfplane Coverage and Related Problems

Authors: Haitao Wang and Jie Xue

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

Abstract
Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O(n^{4/3}log^{5/3}nlog^{O(1)}log n)-time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n^{10/3}2^{O(log^*n)} time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O(nlog n) time, which improves the previously best algorithm of n^{4/3}2^{O(log^*n)} time and matches an Ω(nlog n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O(nlog n) time, which in turn leads to an O(nlog n)-time algorithm for computing an instance-optimal ε-kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O(nklog n)-time algorithm for this problem in SoCG 2023, where k is the size of the ε-kernel; they also raised an open question whether the problem can be solved in O(nlog n) time. Our result thus answers the open question affirmatively.
Cite as

Haitao Wang and Jie Xue. Algorithms for Halfplane Coverage and Related Problems. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2024.79,
  author =	{Wang, Haitao and Xue, Jie},
  title =	{{Algorithms for Halfplane Coverage and Related Problems}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{79:1--79:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.79},
  URN =		{urn:nbn:de:0030-drops-200248},
  doi =		{10.4230/LIPIcs.SoCG.2024.79},
  annote =	{Keywords: halfplane coverage, circular coverage, star-shaped polygon coverage, \epsilon-kernels}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.58
Algorithms for Computing Closest Points for Segments

Authors: Haitao Wang

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
Given a set P of n points and a set S of n segments in the plane, we consider the problem of computing for each segment of S its closest point in P. The previously best algorithm solves the problem in n^{4/3}2^{O(log^*n)} time [Bespamyatnikh, 2003] and a lower bound (under a somewhat restricted model) Ω(n^{4/3}) has also been proved. In this paper, we present an O(n^{4/3}) time algorithm and thus solve the problem optimally (under the restricted model). In addition, we also present data structures for solving the online version of the problem, i.e., given a query segment (or a line as a special case), find its closest point in P. Our new results improve the previous work.
Cite as

Haitao Wang. Algorithms for Computing Closest Points for Segments. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.STACS.2024.58,
  author =	{Wang, Haitao},
  title =	{{Algorithms for Computing Closest Points for Segments}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.58},
  URN =		{urn:nbn:de:0030-drops-197683},
  doi =		{10.4230/LIPIcs.STACS.2024.58},
  annote =	{Keywords: Closest points, Voronoi diagrams, Segment dragging queries, Hopcroft’s problem, Algebraic decision tree model}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.51
On the Line-Separable Unit-Disk Coverage and Related Problems

Authors: Gang Liu and Haitao Wang

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

Abstract
Given a set P of n points and a set S of m disks in the plane, the disk coverage problem asks for a smallest subset of disks that together cover all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an m^{2/3} n^{2/3} 2^O(log^*(m+n)) + O((n+m)log(n+m)) time algorithm for the problem. This improves the previously best result of O(nm + n log n) time. Our techniques also solve the line-constrained version of the problem, where centers of all disks of S are located on a line 𝓁 while points of P can be anywhere in the plane. Our algorithm runs in O(m√n + (n+m)log(n+m)) time, which improves the previously best result of O(nm log(m+n)) time. In addition, our results lead to an algorithm of n^{10/3} 2^O(log^*n) time for a half-plane coverage problem (given n half-planes and n points, find a smallest subset of half-planes covering all points); this improves the previously best algorithm of O(n⁴log n) time. Further, if all half-planes are lower ones, our algorithm runs in n^{4/3} 2^O(log^*n) time while the previously best algorithm takes O(n²log n) time.
Cite as

Gang Liu and Haitao Wang. On the Line-Separable Unit-Disk Coverage and Related Problems. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2023.51,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{On the Line-Separable Unit-Disk Coverage and Related Problems}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.51},
  URN =		{urn:nbn:de:0030-drops-193535},
  doi =		{10.4230/LIPIcs.ISAAC.2023.51},
  annote =	{Keywords: disk coverage, line-separable, unit-disk, line-constrained, half-planes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.101
Improved Algorithms for Distance Selection and Related Problems

Authors: Haitao Wang and Yiming Zhao

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

Abstract
In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future.
Cite as

Haitao Wang and Yiming Zhao. Improved Algorithms for Distance Selection and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2023.101,
  author =	{Wang, Haitao and Zhao, Yiming},
  title =	{{Improved Algorithms for Distance Selection and Related Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.101},
  URN =		{urn:nbn:de:0030-drops-187544},
  doi =		{10.4230/LIPIcs.ESA.2023.101},
  annote =	{Keywords: Geometric optimization, distance selection, Fr\'{e}chet distance, range searching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.82
Computing the Minimum Bottleneck Moving Spanning Tree

Authors: Haitao Wang and Yiming Zhao

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Given a set P of n points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in O(n²) time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of O(n^{4/3} log³ n) time.
Cite as

Haitao Wang and Yiming Zhao. Computing the Minimum Bottleneck Moving Spanning Tree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.MFCS.2022.82,
  author =	{Wang, Haitao and Zhao, Yiming},
  title =	{{Computing the Minimum Bottleneck Moving Spanning Tree}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.82},
  URN =		{urn:nbn:de:0030-drops-168801},
  doi =		{10.4230/LIPIcs.MFCS.2022.82},
  annote =	{Keywords: minimum spanning tree, moving points, unit-disk range emptiness query, dynamic data structure}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.32
Unit-Disk Range Searching and Applications

Authors: Haitao Wang

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Given a set P of n points in the plane, we consider the problem of computing the number of points of P in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching can be adapted to this problem. For example, by adapting Matoušek’s results, we can build a data structure of O(n) space so that each query can be answered in O(√n) time; alternatively, we can build a data structure of O(n²/log² n) space with O(log n) query time. Our techniques lead to improvements for several other classical problems in computational geometry. 1) Given a set of n unit disks and a set of n points in the plane, the batched unit-disk range counting problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in O(n^{4/3}log n) time. We give a new algorithm of O(n^{4/3}) time, which is optimal as it matches an Ω(n^{4/3})-time lower bound. For small χ, where χ is the number of pairs of unit disks that intersect, we further improve the algorithm to O(n^{2/3}χ^{1/3}+n^{1+δ}) time, for any δ > 0. 2) The above result immediately leads to an O(n^{4/3}) time optimal algorithm for counting the intersecting pairs of circles for a set of n unit circles in the plane. The previous best algorithms solve the problem in O(n^{4/3}log n) deterministic time [Katz and Sharir, 1997] or in O(n^{4/3}log^{2/3} n) expected time by a randomized algorithm [Agarwal, Pellegrini, and Sharir, 1993]. 3) Given a set P of n points in the plane and an integer k, the distance selection problem is to find the k-th smallest distance among all pairwise distances of P. The problem can be solved in O(n^{4/3}log² n) deterministic time [Katz and Sharir, 1997] or in O(nlog n+n^{2/3}k^{1/3}log^{5/3}n) expected time by a randomized algorithm [Chan, 2001]. Our new randomized algorithm runs in O(nlog n +n^{2/3}k^{1/3}log n) expected time. 4) Given a set P of n points in the plane, the discrete 2-center problem is to compute two smallest congruent disks whose centers are in P and whose union covers P. An O(n^{4/3}log⁵ n)-time algorithm was known [Agarwal, Sharir, and Welzl, 1998]. Our techniques yield a deterministic algorithm of O(n^{4/3}log^{10/3} n⋅ (log log n)^{O(1)}) time and a randomized algorithm of O(n^{4/3}log³ n⋅ (log log n)^{1/3}) expected time.
Cite as

Haitao Wang. Unit-Disk Range Searching and Applications. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SWAT.2022.32,
  author =	{Wang, Haitao},
  title =	{{Unit-Disk Range Searching and Applications}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.32},
  URN =		{urn:nbn:de:0030-drops-161926},
  doi =		{10.4230/LIPIcs.SWAT.2022.32},
  annote =	{Keywords: Unit disks, disk range searching, batched range searching, distance selection, discrete 2-center, arrangements, cuttings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.59
An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons

Authors: Haitao Wang

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a set S of m point sites in a simple polygon P of n vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known that the problem has an Ω(n+mlog m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n+mlog m) expected time. The previous best deterministic algorithms solve the problem in O(nlog log n+ mlog m) time [Oh, Barba, and Ahn, SoCG 2016] or in O(n+mlog m+mlog² n) time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of O(n+mlog m) time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
Cite as

Haitao Wang. An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2021.59,
  author =	{Wang, Haitao},
  title =	{{An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.59},
  URN =		{urn:nbn:de:0030-drops-138585},
  doi =		{10.4230/LIPIcs.SoCG.2021.59},
  annote =	{Keywords: farthest-sites, Voronoi diagrams, triple-point geodesic center, simple polygons}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.68
On the Planar Two-Center Problem and Circular Hulls

Authors: Haitao Wang

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

Abstract
Given a set S of n points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of S. Previously, Eppstein [SODA'97] gave a randomized algorithm of O(nlog²n) expected time and Chan [CGTA'99] presented a deterministic algorithm of O(nlog² nlog²log n) time. In this paper, we propose an O(nlog² n) time deterministic algorithm, which improves Chan’s deterministic algorithm and matches the randomized bound of Eppstein. If S is in convex position, we solve the problem in O(nlog nlog log n) deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
Cite as

Haitao Wang. On the Planar Two-Center Problem and Circular Hulls. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2020.68,
  author =	{Wang, Haitao},
  title =	{{On the Planar Two-Center Problem and Circular Hulls}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.68},
  URN =		{urn:nbn:de:0030-drops-122267},
  doi =		{10.4230/LIPIcs.SoCG.2020.68},
  annote =	{Keywords: two-center, disk coverage, circular hulls, dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.69
Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments

Authors: Haitao Wang

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

Abstract
In this paper, we first consider the subpath convex hull query problem: Given a simple path π of n vertices, preprocess it so that the convex hull of any query subpath of π can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90'] proposed a data structure of O(n) space and O(log n log log n) query time; reducing the query time to O(log n) increases the space to O(nlog log n). We present an improved result that uses O(n) space while achieving O(log n) query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in O(log n) time each. Our new result leads to improvements for several other problems. In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of n (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of O(n log n) space that can answer each query in (√n log n) time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to O(n). All these are classical problems that have been studied extensively. Previously data structures of Õ(√n) query time were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.
Cite as

Haitao Wang. Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2020.69,
  author =	{Wang, Haitao},
  title =	{{Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.69},
  URN =		{urn:nbn:de:0030-drops-122275},
  doi =		{10.4230/LIPIcs.SoCG.2020.69},
  annote =	{Keywords: subpath hull queries, convex hulls, compact interval trees, ray-shooting, data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.59
A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains

Authors: Haitao Wang

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Let P be a polygonal domain of h holes and n vertices. We study the problem of constructing a data structure that can compute a shortest path between s and t in P under the L_1 metric for any two query points s and t. To do so, a standard approach is to first find a set of n_s "gateways" for s and a set of n_t "gateways" for t such that there exist a shortest s-t path containing a gateway of s and a gateway of t, and then compute a shortest s-t path using these gateways. Previous algorithms all take quadratic O(n_s * n_t) time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in O(n_s + n_t log n_s) time. As a consequence, we construct a data structure of O(n+(h^2 log^3 h/log log h)) size in O(n+(h^2 log^4 h/log log h)) time such that each query can be answered in O(log n) time.
Cite as

Haitao Wang. A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2019.59,
  author =	{Wang, Haitao},
  title =	{{A Divide-and-Conquer Algorithm for Two-Point L\underline1 Shortest Path Queries in Polygonal Domains}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.59},
  URN =		{urn:nbn:de:0030-drops-104631},
  doi =		{10.4230/LIPIcs.SoCG.2019.59},
  annote =	{Keywords: shortest paths, two-point queries, L\underline1 metric, polygonal domains}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.60
Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs

Authors: Haitao Wang and Jie Xue

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We revisit a classical graph-theoretic problem, the single-source shortest-path (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log^2 n) time using linear space, where n is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič [CGTA'15] which uses O(n^{1+delta}) time and O(n^{1+delta}) space (for any small constant delta>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log^{12+o(1)} n) expected time and O(n log^3 n) space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unit-disk graphs can be solved in O(n log n+f(n)) time. Using the same framework with some new ideas, we also obtain a (1+epsilon)-approximate algorithm for the problem, using O(n log n + n log^2(1/epsilon)) time and linear space. This improves the previous (1+epsilon)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/epsilon)^2 n log n) time and O((1/epsilon)^2 n) space. Because of the Omega(n log n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.
Cite as

Haitao Wang and Jie Xue. Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2019.60,
  author =	{Wang, Haitao and Xue, Jie},
  title =	{{Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{60:1--60:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.60},
  URN =		{urn:nbn:de:0030-drops-104649},
  doi =		{10.4230/LIPIcs.SoCG.2019.60},
  annote =	{Keywords: Single-source shortest paths, Weighted unit-disk graphs, Geometric graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.72
An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Authors: Haitao Wang and Jingru Zhang

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

Abstract
We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in O(n log^2 n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively.
Cite as

Haitao Wang and Jingru Zhang. An O(n log n)-Time Algorithm for the k-Center Problem in Trees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2018.72,
  author =	{Wang, Haitao and Zhang, Jingru},
  title =	{{An O(n log n)-Time Algorithm for the k-Center Problem in Trees}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{72:1--72:15},
  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.72},
  URN =		{urn:nbn:de:0030-drops-87852},
  doi =		{10.4230/LIPIcs.SoCG.2018.72},
  annote =	{Keywords: k-center, trees, facility locations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.60
Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane

Authors: Haitao Wang

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

Abstract
Given a rectilinear domain P of h pairwise-disjoint rectilinear obstacles with a total of n vertices in the plane, we study the problem of computing bicriteria rectilinear shortest paths between two points s and t in P. Three types of bicriteria rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when h is relatively small. For example, for computing a minimum-link shortest s-t path, the previous algorithm runs in O(n log^{3/2} n) time while the time of our new algorithm is O(n + h log^{3/2} h).
Cite as

Haitao Wang. Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2017.60,
  author =	{Wang, Haitao},
  title =	{{Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{60:1--60:16},
  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.60},
  URN =		{urn:nbn:de:0030-drops-71876},
  doi =		{10.4230/LIPIcs.SoCG.2017.60},
  annote =	{Keywords: rectilinear paths, shortest paths, minimum-link paths, bicriteria paths, rectilinear polygons}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.61
Quickest Visibility Queries in Polygonal Domains

Authors: Haitao Wang

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

Abstract
Let s be a point in a polygonal domain P of h-1 holes and n vertices. We consider the following quickest visibility query problem. Given a query point q in P, the goal is to find a shortest path in P to move from s to see q as quickly as possible. Previously, Arkin et al. (SoCG 2015) built a data structure of size O(n^2 2^alpha(n) log n) that can answer each query in O(K log^2 n) time, where alpha(n) is the inverse Ackermann function and K is the size of the visibility polygon of q in P (and K can be Theta(n) in the worst case). In this paper, we present a new data structure of size O(n log h + h^2) that can answer each query in O(h log h log n) time. Our result improves the previous work when h is relatively small. In particular, if h is a constant, then our result even matches the best result for the simple polygon case (i.e., h = 1), which is optimal. As a by-product, we also have a new algorithm for the following shortest-path-to-segment query problem. Given a query line segment tau in P, the query seeks a shortest path from s to all points of tau. Previously, Arkin et al. gave a data structure of size O(n^2 2^alpha(n) log n) that can answer each query in O(log^2 n) time, and another data structure of size O(n^3 log n) with O(log n) query time. We present a data structure of size O(n) with query time O(h log n/h), which favors small values of h and is optimal when h = O(1).
Cite as

Haitao Wang. Quickest Visibility Queries in Polygonal Domains. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2017.61,
  author =	{Wang, Haitao},
  title =	{{Quickest Visibility Queries in Polygonal Domains}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{61:1--61:16},
  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.61},
  URN =		{urn:nbn:de:0030-drops-71863},
  doi =		{10.4230/LIPIcs.SoCG.2017.61},
  annote =	{Keywords: shortest paths, visibility, quickest visibility queries, shortest path to segments, polygons with holes}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.11
k-Regret Minimizing Set: Efficient Algorithms and Hardness

Authors: Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.
Cite as

Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. k-Regret Minimizing Set: Efficient Algorithms and Hardness. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICDT.2017.11,
  author =	{Cao, Wei and Li, Jian and Wang, Haitao and Wang, Kangning and Wang, Ruosong and Chi-Wing Wong, Raymond and Zhan, Wei},
  title =	{{k-Regret Minimizing Set: Efficient Algorithms and Hardness}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.11},
  URN =		{urn:nbn:de:0030-drops-70569},
  doi =		{10.4230/LIPIcs.ICDT.2017.11},
  annote =	{Keywords: multi-criteria decision-making, regret minimizing set, top-k query}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.52
Dispersing Points on Intervals

Authors: Shimin Li and Haitao Wang

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

Abstract
We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle.
Cite as

Shimin Li and Haitao Wang. Dispersing Points on Intervals. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ISAAC.2016.52,
  author =	{Li, Shimin and Wang, Haitao},
  title =	{{Dispersing Points on Intervals}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{52:1--52: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.52},
  URN =		{urn:nbn:de:0030-drops-68248},
  doi =		{10.4230/LIPIcs.ISAAC.2016.52},
  annote =	{Keywords: dispersing points, intervals, min-max, algorithms, cycles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.50
epsilon-Kernel Coresets for Stochastic Points

Authors: Lingxiao Huang, Jian Li, Jeff M. Phillips, and Haitao Wang

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms for geometric or combinatorial optimization problems over such data. In this paper, we initiate the study of constructing epsilon-kernel coresets for uncertain points. We consider uncertainty in the existential model where each point's location is fixed but only occurs with a certain probability, and the locational model where each point has a probability distribution describing its location. An epsilon-kernel coreset approximates the width of a point set in any direction. We consider approximating the expected width (an epsilon-EXP-KERNEL), as well as the probability distribution on the width (an (epsilon, tau)-QUANT-KERNEL) for any direction. We show that there exists a set of O(epsilon^{-(d-1)/2}) deterministic points which approximate the expected width under the existential and locational models, and we provide efficient algorithms for constructing such coresets. We show, however, it is not always possible to find a subset of the original uncertain points which provides such an approximation. However, if the existential probability of each point is lower bounded by a constant, an epsilon-EXP-KERNEL is still possible. We also provide efficient algorithms for construct an (epsilon, tau)-QUANT-KERNEL coreset in nearly linear time. Our techniques utilize or connect to several important notions in probability and geometry, such as Kolmogorov distances, VC uniform convergence and Tukey depth, and may be useful in other geometric optimization problem in stochastic settings. Finally, combining with known techniques, we show a few applications to approximating the extent of uncertain functions, maintaining extent measures for stochastic moving points and some shape fitting problems under uncertainty.
Cite as

Lingxiao Huang, Jian Li, Jeff M. Phillips, and Haitao Wang. epsilon-Kernel Coresets for Stochastic Points. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ESA.2016.50,
  author =	{Huang, Lingxiao and Li, Jian and Phillips, Jeff M. and Wang, Haitao},
  title =	{{epsilon-Kernel Coresets for Stochastic Points}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.50},
  URN =		{urn:nbn:de:0030-drops-63921},
  doi =		{10.4230/LIPIcs.ESA.2016.50},
  annote =	{Keywords: e-kernel, coreset, stochastic point, shape fitting}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.77
On the Geodesic Centers of Polygonal Domains

Authors: Haitao Wang

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in O(n^{11}*log(n)) time. Previously, an algorithm of O(n^{12+epsilon}) time was known for this problem, for any epsilon > 0.
Cite as

Haitao Wang. On the Geodesic Centers of Polygonal Domains. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.ESA.2016.77,
  author =	{Wang, Haitao},
  title =	{{On the Geodesic Centers of Polygonal Domains}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.77},
  URN =		{urn:nbn:de:0030-drops-64189},
  doi =		{10.4230/LIPIcs.ESA.2016.77},
  annote =	{Keywords: geodesic centers, shortest paths, polygonal domains}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.14
Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

Authors: Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains.
Cite as

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang. Computing the L1 Geodesic Diameter and Center of a Polygonal Domain. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wonbae_et_al:LIPIcs.STACS.2016.14,
  author =	{Won Bae, Sang and Korman, Matias and Mitchell, Joseph S. B. and Okamoto, Yoshio and Polishchuk, Valentin and Wang, Haitao},
  title =	{{Computing the L1 Geodesic Diameter and Center of a Polygonal Domain}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.14},
  URN =		{urn:nbn:de:0030-drops-57151},
  doi =		{10.4230/LIPIcs.STACS.2016.14},
  annote =	{Keywords: geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.293
L_1 Shortest Path Queries among Polygonal Obstacles in the Plane

Authors: Danny Z. Chen and Haitao Wang

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, after the free space is triangulated, we present an O(n+h log h) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of the L_1 shortest obstacle-avoiding path from s to t can be reported in O(log n) time and the actual path can be found in additional time proportional to the number of edges of the path. Previously, the best algorithm computes such a shortest path map in O(n log n) time and O(n) space. In addition, our techniques also yield an improved algorithm for computing the L_1 geodesic Voronoi diagram of m point sites among the obstacles.
Cite as

Danny Z. Chen and Haitao Wang. L_1 Shortest Path Queries among Polygonal Obstacles in the Plane. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 293-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2013.293,
  author =	{Chen, Danny Z. and Wang, Haitao},
  title =	{{L\underline1 Shortest Path Queries among Polygonal Obstacles in the Plane}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{293--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.293},
  URN =		{urn:nbn:de:0030-drops-39425},
  doi =		{10.4230/LIPIcs.STACS.2013.293},
  annote =	{Keywords: computational geometry, shortest path queries, shortest paths among obstacles, \$L\underline1\$/\$L\underlineinfty\$/rectilinear metric, shortest path maps, geodesic Vorono}
}
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