Let S be a set of n points in a polygon P with m vertices. The geodesic unit-disk graph G(S) induced by S has vertex set S and contains an edge between two vertices whenever their geodesic distance in P is at most one. In the weighted version, each edge is assigned weight equal to the geodesic distance between its endpoints; in the unweighted version, every edge has weight 1. Given a source point s ∈ S, we study the problem of computing shortest paths from s to all vertices of G(S). To the best of our knowledge, this problem has not been investigated previously. A naive approach constructs G(S) explicitly and then applies a standard shortest path algorithm for general graphs, but this requires quadratic time in the worst case, since G(S) may contain Ω(n²) edges. In this paper, we give the first subquadratic-time algorithms for this problem. For the weighted case, when P is a simple polygon, we obtain an O(m + n log³ n log² m)-time algorithm. For the unweighted case, we provide an O(m + n log n log² m)-time algorithm for simple polygons, and an O(√n (n+m)log(n+m))-time algorithm for polygons with holes.

Given a set of m points and a set of n lines in the plane, we consider the classical problem of computing the faces of the arrangement of the lines that contain at least one point. We present an algorithm of O(m^{2/3} n^{2/3} + (n+m)log n) time for the problem. We also prove that this matches the lower bound under the algebraic decision tree model and thus our algorithm is optimal. In particular, when m = n, the runtime is O(n^{4/3}), which matches the worst case combinatorial complexity Ω(n^{4/3}) of all output faces. This is the first optimal algorithm since the problem was first studied more than three decades ago [Edelsbrunner, Guibas, and Sharir, SoCG 1988].

Given a polygonal domain 𝒫 in the plane, the shortest path map with respect to a point s, denoted by SPM(s), is the decomposition of 𝒫 into cells such that shortest paths from s to all points t in the same cell have the same vertex sequence. The shortest path map equivalence decomposition of 𝒫 is the decomposition of 𝒫 into cells so that SPM(s) is topologically equivalent for all points s in the same cell. In this paper, we prove new upper bounds on the combinatorial complexities of the SPM-equivalence decompositions under various settings, depending on whether s and/or t are restricted to be the boundary of 𝒫. We also propose new algorithms to compute these decompositions. Further, our results lead to new solutions to several other problems, including answering two-point shortest path queries in 𝒫, and computing geodesic diameter and center of 𝒫.

Given a simple polygon P with n vertices, we consider the problem of constructing a data structure for visibility queries: for any query point q ∈ P, compute the visibility polygon of q in P. To obtain O(log n + k) query time, where k is the size of the visibility polygon of q, the previous best result requires O(n³) space. In this paper, we propose a new data structure that uses O(n^{2+ε}) space, for any ε > 0, while achieving the same query time. If only O(n²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) space, the only previously known approach, aside from the O(n)-time algorithm that computes the visibility polygon without preprocessing, is an O(n)-space data structure that supports O(k log n)-time queries. We construct a data structure using O(n log n) space that answers visibility queries in O(n^{1/2+ε} + k) time. In addition, for the special case in which q lies on the boundary of P, we build a data structure of O(n log n) space supporting O(log² n + k) query time; alternatively, we achieve O(log n + k) query time using O(n^{1+ε}) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Chan [J. ACM, 2010] developed a data structure to maintain the convex hull of a dynamic set of points in 3D under insertions and deletions and answer certain queries on the convex hulls. The algorithm has been slightly improved by Kaplan, Mulzer, Roditty, Seiferth, and Sharir [Discret. Comput. Geom., 2020] and by Chan [Discret. Comput. Geom., 2020], without altering the main algorithmic framework. The current best result supports each insertion in \(O(\log^2 n)\) amortized time, each deletion in \(O(\log^4 n)\) amortized time, and each extreme query in \(O(\log^2 n)\) worst-case time (along with other query types). These results have numerous applications, notably in dynamic Euclidean nearest neighbor searching in 2D. In the dual setting, the problem becomes maintaining the lower envelope of a dynamic set of 3D planes for vertical ray-shooting queries. By developing randomized vertical shallow cutting algorithms for general distance functions, Kaplan, Mulzer, Roditty, Seiferth, and Sharir [Discret. Comput. Geom., 2020] and Liu [SIAM J. Comput., 2022] extended Chan's framework to maintain the lower envelope of a dynamic set of general 3D surfaces. The best known result in this setting achieves \(O(\log^2 n)\) amortized expected time for insertions, \(O(\log^4 n)\) amortized expected time for deletions, and \(O(\log^2 n)\) worst-case time for vertical ray-shooting queries. As an immediate application, dynamic nearest neighbor searching under general distance functions (e.g., the \(L_p\) metric or additively-weighted Euclidean distance) can be solved.

Given a set of n circular arcs of the same radius in the plane, we consider the problem of computing the number of intersections among the arcs. The problem was studied before and the previously best algorithm solves the problem in O(n^{4/3+ε}) time [Agarwal, Pellegrini, and Sharir, SIAM J. Comput., 1993], for any constant ε > 0. No progress has been made on the problem for more than 30 years. We present a new algorithm of O(n^{4/3}log^{16/3} n) time and improve it to O(n^{1+ε}+K^{1/3}n^{2/3}((n²)/(n+K))^{ε}log^{16/3}n) time for small K, where K is the number of intersections of all arcs.

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, which matches the above lower bound. 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.

Given in the plane a set S of n points and a set of disks centered at these points, the disk graph G(S) induced by these disks has vertex set S and an edge between two vertices if their disks intersect. Note that the disks may have different radii. We consider the problem of computing shortest paths from a source point s ∈ S to all vertices in G(S) where the length of a path in G(S) is defined as the number of edges in the path. The previously best algorithm solves the problem in O(nlog² n) time. A lower bound of Ω(nlog n) is also known for this problem under the algebraic decision tree model. In this paper, we present an O(nlog n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple.

Let $\mathcal{P}$ be the surface of a convex polyhedron of n vertices. We consider the two-point shortest path query problem for $\mathcal{P}$: Constructing a data structure so that given any two query points s and t on $\mathcal{P}$, a shortest path from s to t on $\mathcal{P}$ can be computed efficiently. To achieve $O(\log n)$ query time (for computing the shortest path length), the previously best result uses $O\left(n^{8+\epsilon}\right)$ preprcessing time and space [Aggarwal, Aronov, O’Rourke, and Schevon, SICOMP 1997], where $\epsilon$ is an arbitrarily small positive constant. In this paper, we present a new data structure of $O\left(n^{6+\frac{2}{3}+\epsilon}\right)$ preprocessing time and space, with $O(\log n)$ query time. For a special case where one query point is required to be on an edge of $\mathcal{P}$, the previously best work uses $O\left(n^{6+\epsilon}\right)$ preprcessing time and space to achieve $O(\log n)$ query time. We improve the preprocessing time and space to $O\left(n^{5+\frac{1}{4}+\epsilon}\right)$, with $O(\log n)$ query time. If both query points are on the edges of $\mathcal{P}$, then we can answer each query in $O(\log n)$ time with $O\left(n^{5+\epsilon}\right)$ space and preprocessting time. Furthermore, we present a new algorithm to compute the exact set of shortest path edge sequences of $\mathcal{P}$, which are known to be $\Theta\left(n^{4}\right)$ in number and have a total complexity of $\Theta\left(n^{5}\right)$ in the worst case. The previously best algorithm for the problem takes roughly $O\left(n^{6} \log n \log ^{*} n\right)$ time, while our new algorithm runs in $O\left(n^{5+\epsilon}\right)$ time.

A long-standing belief holds that Bayesian Optimization (BO) with standard Gaussian processes (GP) --- referred to as standard BO --- underperforms in high-dimensional optimization problems. While this belief seems plausible, it lacks both robust empirical evidence and theoretical justification. To address this gap, we present a systematic investigation. First, through a comprehensive evaluation across twelve benchmarks, we found that while the popular Square Exponential (SE) kernel often leads to poor performance, using Mat\'ern kernels enables standard BO to consistently achieve top-tier results, frequently surpassing methods specifically designed for high-dimensional optimization. Second, our theoretical analysis reveals that the SE kernel’s failure primarily stems from improper initialization of the length-scale parameters, which are commonly used in practice but can cause gradient vanishing in training. We provide a probabilistic bound to characterize this issue, showing that Mat\'ern kernels are less susceptible and can robustly handle much higher dimensions. Third, we propose a simple robust initialization strategy that dramatically improves the performance of the SE kernel, bringing it close to state-of-the-art methods, without requiring additional priors or regularization. We prove another probabilistic bound that demonstrates how the gradient vanishing issue can be effectively mitigated with our method. Our findings advocate for a re-evaluation of standard BO’s potential in high-dimensional settings.

For a set P of n points in the plane and a value r > 0, the unit-disk range reporting problem is to construct a data structure so that given any query disk of radius r, all points of P in the disk can be reported efficiently. We consider the dynamic version of the problem where point insertions and deletions of P are allowed. The previous best method provides a data structure of O(n log n) space that supports O(log^{3+ε} n) amortized insertion time, O(log^{5+ε} n) amortized deletion time, and O(log² n/log log n+k) query time, where ε is an arbitrarily small positive constant and k is the output size. In this paper, we improve the query time to O(log n+k) while keeping other complexities the same as before. A key ingredient of our approach is a shallow cutting algorithm for circular arcs, which may be interesting in its own right. A related problem that can also be solved by our techniques is the dynamic unit-disk range emptiness queries: Given a query unit disk, we wish to determine whether the disk contains a point of P. The best previous work can maintain P in a data structure of O(n) space that supports O(log² n) amortized insertion time, O(log⁴n) amortized deletion time, and O(log² n) query time. Our new data structure also uses O(n) space but can support each update in O(log^{1+ε} n) amortized time and support each query in O(log n) time.

Given a set P of n points in the plane, its unit-disk graph G(P) is a graph with P as its vertex set such that two points of P are connected by an edge if their (Euclidean) distance is at most 1. We consider several classical problems on G(P) in a special setting when points of P are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. ● For the problem of finding the smallest dominating set of G(P), we present an O(knlog n) time algorithm, where k is the smallest dominating set size. We also consider the weighted case in which each point of P has a weight and the goal is to find a dominating set in G(P) with minimum total weight; our algorithm runs in O(n³log² n) time. In particular, for a given k, our algorithm can compute in O(kn²log² n) time a minimum weight dominating set of size at most k (if it exists). ● For the discrete k-center problem, which is to find a subset of k points in P (called centers) for a given k, such that the maximum distance between any point in P and its nearest center is minimized. We present an algorithm that solves the problem in O(min{n^{4/3}log n+knlog² n,k² nlog²n}) time, which is O(n²log² n) in the worst case when k = Θ(n). For comparison, the runtime of the current best algorithm for the continuous version of the problem where centers can be anywhere in the plane is O(n³ log n). ● For the problem of finding a maximum independent set in G(P), we give an algorithm of O(n^{7/2}) time and another randomized algorithm of O(n^{37/11}) expected time, which improve the previous best result of O(n⁶log n) time. Our algorithms can be extended to compute a maximum-weight independent set in G(P) with the same time complexities when points of P have weights. - If we are looking for an (unweighted) independent set of size 3, we derive an algorithm of O(nlog n) time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position). - If points of P have weights and are not necessarily in convex position, we present an algorithm that can find a maximum-weight independent set of size 3 in O(n^{5/3+δ}) time for an arbitrarily small constant δ > 0. By slightly modifying the algorithm, a maximum-weight clique of size 3 can also be found within the same time complexity. ● For the dispersion problem, which is to find a subset of k points from P for a given k, such that the minimum pairwise distance of the points in the subset is maximized. We present an algorithm of O(n^{7/2}log n) time and another randomized algorithm of O(n^{37/11}log n) expected time, which improve the previous best result of O(n⁶) time. - If k = 3, we present an algorithm of O(nlog² n) time and another randomized algorithm of O(nlog n) expected time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position).

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}n\log^{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(n\log n)$ time, which improves the previously best algorithm of $n^{4/3}2^{O(\log^*n)}$ time and matches an $Ω(n\log n)$ lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in $O(n\log n)$ time, which in turn leads to an $O(n\log 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(nk\log 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(n\log n)$ time. Our result thus answers the open question affirmatively.

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.

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(n\log n)$-time algorithm for planar two-center, matching the $Ω(n\log 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(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.

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.

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 $\ell$. We present an $O(n^{3/2}\log^2 n)$ time algorithm for the problem. This improves the previously best work of $O(n^2\log n)$ time. Our result leads to an algorithm of $O(n^{{7}/{2}}\log^2 n)$ time for the halfplane coverage problem (i.e., using $n$ weighted halfplanes to cover $n$ points), an improvement over the previous $O(n^4\log n)$ time solution. If all halfplanes are lower ones, our algorithm runs in $O(n^{{3}/{2}}\log^2 n)$ time, while the previous best algorithm takes $O(n^2\log n)$ time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities.

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.

Abstract. In this paper, we first consider the subpath convex hull query problem: Given a simple path [Formula: see text] of [Formula: see text] vertices, preprocess it so that the convex hull of any query subpath of [Formula: see text] can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [ Int. J. Comput. Geom. Appl., 1 (1991), pp. 1–22; first appeared in SODA 1990] proposed a data structure of [Formula: see text] space and [Formula: see text] query time; they also reduced the query time to [Formula: see text] by increasing the space to [Formula: see text]. We present an improved result that uses [Formula: see text] space while achieving [Formula: see text] 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 [Formula: see text] time each. The preprocessing time of our data structure is [Formula: see text] after the vertices of [Formula: see text] are sorted by [Formula: see text]-coordinate. As the subpath convex hull query problem has many applications, our new result leads to improvements for several other problems. In particular, with the help of the above result, along with other techniques, we present new algorithms for the ray-shooting problem among segments. Given a set of [Formula: see text] (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 [Formula: see text] space that can answer each query in [Formula: see text] time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to [Formula: see text]. As a by-product, given a set of [Formula: see text] (possibly intersecting) segments in the plane, we build a data structure of [Formula: see text] space that can determine whether a query line intersects a segment in [Formula: see text] time. The preprocessing time is [Formula: see text] for all four problems, which can be reduced to [Formula: see text] time by a randomized algorithm so that the query time is bounded by [Formula: see text] with high probability. All these are classical problems that have been studied extensively. Previously data structures of [Formula: see text] query time were known in the early 1990s (the notation [Formula: see text] suppresses a polylogarithmic factor); nearly no progress has been made for more than two decades. For all these problems, our new 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.

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.

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 $\ell$. We present an $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 $\ell$ while points of $P$ can be anywhere in the plane. Our algorithm runs in $O((n+m)\log (m+ n)+m \log m\log n)$ time, which improves the previously best result of $O(nm\log(m+n))$ time. In addition, our results lead to an algorithm of $O(n^3\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^4\log n)$ time. Further, if all half-planes are lower ones, our algorithm runs in $O(n\log n)$ time while the previously best algorithm takes $O(n^2\log n)$ time.

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (inSIAM Journal on Computing, 1999) gave an algorithm ofO(nlogn) time andO(nlogn) space, wherenis the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space toO(n)while the runtime of the algorithm is stillO(nlogn). In this article, we present a new algorithm ofO(n+hlogh) time andO(n)space, provided that a triangulation of the free space is given, wherehis the number of obstacles. The algorithm is better than the previous work whenhis relatively small. Our algorithm builds a shortest path map for a source pointsso that given any query pointt, the shortest path length fromstotcan be computed inO(logn) time and a shortests-tpath can be produced in additional time linear in the number of edges of the path.

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^2)$ 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^3 n)$ time.

We present new algorithms for computing many faces in arrangements of lines and segments. Given a set S of n lines (resp., segments) and a set P of m points in the plane, the problem is to compute the faces of the arrangements of S that contain at least one point of P. For the line case, we give a deterministic algorithm of time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log2.22 n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log1/3 n in certain cases (e.g., when m = Θ(n)). For the segment case, we present a deterministic algorithm of time, where and α(n) is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log2.11 n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log n in certain cases (e.g., when m = Θ(n)). We also give a randomized algorithm of O(m2/3 K1/3 log n + τ(nα(n) + n log m + m) log n log K) expected time, where K is the number of intersections of all segments of S. In addition, we consider the query version of the problem, that is, preprocess S to compute the face of the arrangement of S that contains any query point. We present new results that improve the previous work for both the line and the segment cases.

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+m\log m)$ time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in $O(n+m\log m)$ expected time. The previous best deterministic algorithms solve the problem in $O(n\log \log n+ m\log m)$ time [Oh, Barba, and Ahn, SoCG 2016] or in $O(n+m\log m+m\log^2 n)$ time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of $O(n+m\log m)$ time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(n log n) is a lower bound. It has been an open problem for over two decades whether the space can be reduced to O(n). In this paper, we settle it by solving the problem in O(n log n) time and O(n) space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point s in O(n log n) time and O(n) space, such that given any query point t, the length of a shortest path from s to t can be computed in O(log n) time and a shortest path can be produced in additional time linear in the number of edges of the path.

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of O(nlogn) time and O(nlogn) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang [SODA 2021] reduced the space to O(n) while the runtime of the algorithm is still O(nlogn). In this paper, we present a new algorithm of O(n+hlogh) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. Our algorithm builds a shortest path map for a source point s, so that given any query point t, the shortest path length from s to t can be computed in O(logn) time and a shortest s-t path can be produced in additional time linear in the number of edges of the path.

We consider a classical $k$-center problem in trees. Let $T$ be a tree of $n$ vertices such that 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., 12 (1983), pp. 751--758] 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.

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(n\log^2n)$ expected time and Chan [CGTA'99] presented a deterministic algorithm of $O(n\log^2 n\log^2\log n)$ time. In this paper, we propose an $O(n\log^2 n)$ time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(n\log n\log\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.

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(n\log\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 $(\sqrt{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 $\widetilde{O}(\sqrt{n})$ query time (the notation $\widetilde{O}$ suppresses a polylogarithmic factor) 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.

Let $\mathcal{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 $\mathcal{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\cdot 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.

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.

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.

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).

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).

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.

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.

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.

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.

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.

Geometric range search is a fundamental primitive for spatial data analysis in SQL and NoSQL databases. It has extensive applications in location-based services, computer-aided design, and computational geometry. Due to the dramatic increase in data size, it is necessary for companies and organizations to outsource their spatial data sets to third-party cloud services (e.g., Amazon) in order to reduce storage and query processing costs, but, meanwhile, with the promise of no privacy leakage to the third party. Searchable encryption is a technique to perform meaningful queries on encrypted data without revealing privacy. However, geometric range search on spatial data has not been fully investigated nor supported by existing searchable encryption schemes. In this paper, we design a symmetric-key searchable encryption scheme that can support geometric range queries on encrypted spatial data. One of our major contributions is that our design is a general approach, which can support different types of geometric range queries. In other words, our design on encrypted data is independent from the shapes of geometric range queries. Moreover, we further extend our scheme with the additional use of tree structures to achieve search complexity that is faster than linear. We formally define and prove the security of our scheme with indistinguishability under selective chosen-plaintext attacks, and demonstrate the performance of our scheme with experiments in a real cloud platform (Amazon EC2).

Searchable encryption is a promising technique enabling meaningful search operations to be performed on encrypted databases while protecting user privacy from untrusted third-party service providers. However, while most of the existing works focus on common SQL queries, geometric queries on encrypted spatial data have not been well studied. Especially, circular range search is an important type of geometric query on spatial data which has wide applications, such as proximity testing in Location-Based Services and Delaunay triangulation in computational geometry. In this poster, we propose two novel symmetric-key searchable encryption schemes supporting circular range search. Informally, both of our schemes can correctly verify whether a point is inside a circle on encrypted spatial data without revealing data privacy or query privacy to a semi-honest cloud server. We formally define the security of our proposed schemes, prove that they are secure under Selective Chosen-Plaintext Attacks, and evaluate their performance through experiments in a real-world cloud platform (Amazon EC2). To the best of our knowledge, this work represents the first study in secure circular range search on encrypted spatial data.

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem version on curved obstacles, which are commonly modeled as splinegons . A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons), and the combinatorial complexity of each curved edge is assumed to be O (1). Given in the plane two points s and t and a set s of h pairwise disjoint splinegons with a total of n vertices, after a bounded degree decomposition of S is obtained, we compute a shortest s -to- t path avoiding the splinegons in O ( n + h log h + k ) time, where k is a parameter sensitive to the geometric structures of the input and is upper bounded by O ( h 2 ). The bounded degree decomposition of S , which is similar to the triangulation of the polygonal domains, can be computed in O ( n log n ) time or O ( n + h log 1 + ϵ h ) time for any ϵ > 0. In particular, when all splinegons are convex, the decomposition can be computed in O ( n + h log h ) time and k is linear to the number of common tangents in the free space (called “free common tangents”) among the splinegons. Our techniques also improve several previous results: (1) For the polygon case (i.e., when all splinegons are polygons), the shortest path problem was previously solved in O ( n log n ) time, or in O ( n + h 2 log n ) time. Thus, our algorithm improves the O ( n + h 2 log n ) time result, and is faster than the O ( n log n ) time solution for sufficiently small h , for example, h = o (√ n ,log n . (2) Our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among h pairwise disjoint convex splinegons with a total of n vertices. Our algorithm runs in O ( n + h log h + k ) time and O ( n ) working space, where k is the number of all free common tangents. Note that k = O ( h 2 ). Even for the special case where all splinegons are convex polygons , the previously best algorithm for this visibility problem takes O ( n + h 2 log n ) time. (3) We improve the previous work for computing the shortest path between two points among convex pseudodisks of O (1) complexity each. In addition, a by-product of our techniques is an optimal O ( n + h log h ) time and O ( n ) space algorithm for computing the Voronoi diagram of a set of h pairwise disjoint convex splinegons with a total of n vertices.

Cloud computing promises users massive scale outsourced data storage services with much lower costs than traditional methods. However, privacy concerns compel sensitive data to be stored on the cloud server in an encrypted form. This posts a great challenge for effectively utilizing cloud data, such as executing common SQL queries. A variety of searchable encryption techniques have been proposed to solve this issue; yet efficiency and scalability are still the two main obstacles for their adoptions in real-world datasets, which are multi-dimensional in general. In this paper, we propose a tree-based public-key Multi-Dimensional Range Searchable Encryption (MDRSE) to overcome the above limitations. Specifically, we first formally define the leakage function and security of a tree-based MDRSE. Then, by leveraging an existing predicate encryption in a novel way, our tree-based MDRSE efficiently indexes and searches over encrypted cloud data with multi-dimensional tree structures (i.e., R-trees). Moreover, our scheme is able to protect single-dimensional privacy while previous efficient solutions fail to achieve. Our scheme is selectively secure, and through extensive experimental evaluation on a large-scale real-world dataset, we show the efficiency and scalability of our scheme.

Let P be a set of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane. In this paper, we consider the problem of building a data structure that can quickly compute an L1 shortest obstacle-avoiding path between any two query points s and t. We build a data structure of size O(n + h2 · log h · 4√log h) in O(n + h2 · log2 h · 4√log h) time that answers each query in O(log n + k) time, where k is the number of edges of the output path. Note that n + h2 · log2 h · 4√log h = O(n+h2+ϵ) for any constant ϵ > 0. We also extend our techniques to the weighted rectilinear version in which the "obstacles" of P are rectilinear regions with "weights" and allow L1 paths to travel through them with weighted costs. Our algorithm answers each query in O(log n + k) time with a data structure of size O(n2 · log n · 4√log n) that is built in O(n2 · log2 n · 4√log n) time.

In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of h pairwise disjoint splinegons with a total of n vertices, we present an algorithm that can compute a shortest path from s to t avoiding the splinegons in O(n+hlogεh+k) time for any ε>0, where k is a parameter sensitive to the input splinegons and k=O(h2). If all splinegons are convex, a common tangent of two splinegons is "free" if it does not intersect the interior of any splingegon; our techniques yield an output sensitive algorithm for computing all free common tangents of the h splinegons in O(n+hlogh+k) time and O(n) working space, where k is the number of all free common tangents.

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.

Multiple objects in the plane are called pseudodisks if the boundaries of any two of them intersect transversely at most twice. Given a set of $n$ (possibly intersecting) convex pseudodisks of $O(1)$ complexity each and two points $s$ and $t$ in the plane, we present an efficient algorithm for computing a shortest $s$-to-$t$ path avoiding the pseudodisks. After the union of the pseudodisks is computed, which can be done in $O(n\log n)$ randomized time or $O(n\log^2 n)$ deterministic time, our algorithm runs in $O(n\log n+k)$ deterministic time, where $k$ is the size of the extended visibility graph of the union of the pseudodisks. Note that $k = O(n^2)$ in the worst case. In over two decades, the previously best algorithms for this problem have not improved on the bound of $O(n^2\log n)$ time, even when all the pseudodisks are pairwise disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution and settling an open problem posed in 1988. Our algorithm actually solves a more general version of the open problem. Further, as a byproduct of our approach, we present an $O(n\log n + k)$-time algorithm for computing the extended visibility graph of a set of $n$ (possibly intersecting) convex pseudodisks in the plane. The previously best known time bound for this visibility problem is $O(n^2 \log n)$.

Multiple objects in the plane are called pseudodisks if they are convex and the boundaries of any two of them intersect transversely at most twice. Given a set of n (possibly intersecting) pseudodisks of O(1) complexity each and two points s and t in the plane, we develop an O(n2) time algorithm for computing a shortest s-to-t path avoiding the pseudodisks. In over two decades, the previously best algorithms for this problem take O(n2 log n) time, even when all pseudodisks are pairwise-disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution. Our algorithm actually solves a more general version of the motion planning problem. Further, as a by-product of our approach, we present an O(n2) time algorithm for computing the visibility graph of a set of n (possibly intersecting) pseudodisks in the plane. The previously best known time bound of this visibility problem is O(n2 log n). In addition, for n pairwise disjoint (non-polygonal) convex objects of O(1) complexity each in the plane, we compute a shortest s-to-t path avoiding all objects in O(n log n + k) time, where k is the size of the visibility graph of the objects.

We consider the practical NP-complete problem of finding a minimum weight spanning tree with both edge weights and inner nodes weights. We present two polynomial time algorithms with approximation factors of 2.35 · ln n and 2Hn, respectively, where n is the number of nodes in the graph and Hn is the n-th Harmonic number. This nearly matches the lower bound of (l-\in )Hn, for any \in \ge 0. We also give an approximation algorithm with approximation factor \Delta - 1, where \Delta is the maximum degree of the graph. For metric spaces, we give a 3.105-approximation algorithm and show that an approximation factor of 1.463 is impossible unless {NP \subseteq DTIME[n^{O(\log longn)} ]}.