21 Search Results for "Wang, Haitao"


Document
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
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-dev.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
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-dev.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
Minimum-Membership Geometric Set Cover, Revisited

Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results. - We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership). - We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.

Cite as

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
  title =	{{Minimum-Membership Geometric Set Cover, Revisited}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11},
  URN =		{urn:nbn:de:0030-drops-178610},
  doi =		{10.4230/LIPIcs.SoCG.2023.11},
  annote =	{Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
The Weighted k-Center Problem in Trees for Fixed k

Authors: Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
We present a linear time algorithm for the weighted k-center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O(n log n) by Wang et al. [Haitao Wang and Jingru Zhang, 2018]. Whether an O(n) time algorithm exists for arbitrary k is still open.

Cite as

Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev. The Weighted k-Center Problem in Trees for Fixed k. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ISAAC.2019.27,
  author =	{Bhattacharya, Binay and Das, Sandip and Dev, Subhadeep Ranjan},
  title =	{{The Weighted k-Center Problem in Trees for Fixed k}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{27:1--27:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.27},
  URN =		{urn:nbn:de:0030-drops-115238},
  doi =		{10.4230/LIPIcs.ISAAC.2019.27},
  annote =	{Keywords: facility location, prune and search, parametric search, k-center problem, conditional k-center problem, trees}
}
Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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}
}
  • Refine by Author
  • 19 Wang, Haitao
  • 2 Li, Jian
  • 2 Xue, Jie
  • 2 Zhao, Yiming
  • 1 Bandyapadhyay, Sayan
  • Show More...

  • Refine by Classification
  • 10 Theory of computation → Computational geometry
  • 9 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Network optimization

  • Refine by Keyword
  • 5 shortest paths
  • 3 polygonal domains
  • 2 Voronoi diagrams
  • 2 disk coverage
  • 2 distance selection
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 4 2016
  • 3 2017
  • 3 2019
  • 3 2023
  • 2 2020
  • 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