Search

We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given n points and n lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in O(n4/3) time, which matches the conjectured lower bound and improves the best previous time bound of \(n^{4/3}2^{O(\log ^*n)}\) obtained almost 30 years ago by Matoušek [58]. We describe two interesting and different ways to achieve the result: The first is randomized and uses a new two-dimensional version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman [42]. The second approach extends to any constant dimension. Many consequences follow from these new ideas: For example, we obtain an O(n4/3)-time algorithm for line segment intersection counting in the plane, O(n4/3)-time randomized algorithms for distance selection in the plane and bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with O(n4/3) preprocessing time and space and \(O(n^{1/3})\) query time. [ABSTRACT FROM AUTHOR]

We present new results on a number of fundamental problems about dynamic geometric data structures: (1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n 11 / 12 for (i) and (ii), n 5 / 6 for (iii) and (iv), and n 2 / 3 for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings (Chan in SIAM J. Comput. 32(3), 700–716 (2003)). (2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O (log 2 n) , and the amortized update time is O (log 4 n) instead of O (log 5 n) (Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (2017)). (3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O (log 4 n) instead of O (log 7 n) (Eppstein in Discrete Comput. Geom. 13(1), 111–122 (1995); Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (2017)). [ABSTRACT FROM AUTHOR]

For any constant d and parameter ε ∈(0, 1/2], we show the existence of (roughly) 1/ εd orderings on the unit cube [0, 1)d such that for any two points p, q ∈ [0, 1)d close together under the Euclidean metric, there is a linear ordering in which all points between p and q in the ordering are ``close"" to p or q. More precisely, the only points that could lie between p and q in the ordering are points with Euclidean distance at most ε ||p - q|| from either p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in lowdimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search. [ABSTRACT FROM AUTHOR]

Presents a mathematical solution to maintain a planar convex hull through arbitrary insertions and deletions of points. Significance of the Overmars and Van Leeuwen solutions for queries on bridge-finding proposed in 1981; Data structures; Analysis of algorithms and problem complexity.

Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems time-windowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal et al. (in: Proceedings of the 31st International Symposium on Computational Geometry (SoCG), pp 240–254, 2015). In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al. 's, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for both the time-windowed 2D diameter decision problem and the time-windowed 2D convex hull area decision problem in O (n log n) time, improving Bokal et al. 's O (n log 2 n) and O (n log n log log n) solutions respectively. Our first approach is to reduce time-windowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O (n polylog n) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems. [ABSTRACT FROM AUTHOR]

We revisit the orthogonal range searching problem and the exact ℓ ∞ nearest neighbor searching problem for a static set of n points when the dimension d is moderately large. We give the first data structure with near linear space that achieves truly sublinear query time when the dimension is any constant multiple of log n . Specifically, the preprocessing time and space are O (n 1 + δ) for any constant δ > 0 , and the expected query time is n 1 - 1 / O (c log c) for d = c log n . The data structure is simple and is based on a new "augmented, randomized, lopsided" variant of k-d trees. It matches (in fact, slightly improves) the performance of previous combinatorial algorithms that work only in the case of offline queries [(Impagliazzo et al. in arXiv:1401.5512, 2014) and (Chan in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015)]. It leads to slightly faster combinatorial algorithms for all-pairs shortest paths in general real-weighted graphs and rectangular Boolean matrix multiplication. In the offline case, we show that the problem can be reduced to the Boolean orthogonal vectors problem and thus admits an n 2 - 1 / O (log c) -time non-combinatorial algorithm [Abboud et al. in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015]. This reduction is also simple and is based on range trees. Finally, we use a similar approach to obtain a small improvement to Indyk's data structure (J Comput Syst Sci 63(4):627–638, 2001) for approximate ℓ ∞ nearest neighbor search when d = c log n . [ABSTRACT FROM AUTHOR]

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in O(log n(log log n)²) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n factors. We further show how to reduce the query time to O(log n log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log1+ε n) for any constant ε > 0, or vice versa. [ABSTRACT FROM AUTHOR]

Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and Δ over time, our KDS uses O(nlogΔ) space and processes O(n2βlogΔlogn+n2βlogΔloglogΔ) events, each in worst-case time O(log2n+log2logΔ). Here, β is an extremely slow-growing function. The locality of the KDS is O(logn+loglogΔ). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time O(logΔlog2n+logΔlog2logΔ). Also, we use a similar approach to provide a KDS for the all ε-nearest neighbors in Rd. The complexities of the previous KDSs, for both closest pair and all ε-nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming Δ is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work. [ABSTRACT FROM AUTHOR]

Given a set of n moving points in R d , where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O ˜ ( n 5 / 3 ) -time algorithm 1 to compute a ( 1 + ϵ ) -factor approximation to the minimum closest pair distance over time, for any constant ϵ > 0 and any constant dimension d . This addresses an open problem posed by Gupta, Janardan, and Smid [1] . More generally, we consider a data structure version of the problem: for any linearly moving query point q , we want a ( 1 + ϵ ) -factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O ˜ ( n 5 / 3 ) space and O ˜ ( n 2 / 3 ) query time, O ˜ ( n 5 ) space and polylogarithmic query time, or O ˜ ( n ) space and O ˜ ( n 4 / 5 ) query time, for any constant ϵ > 0 and any constant dimension d . 1 The notation O ˜ is used to hide polylogarithmic factors. That is, O ˜ ( f ( n ) ) = O ( f ( n ) log c ⁡ n ) , where c is a constant. [ABSTRACT FROM AUTHOR]

We give a fully dynamic data structure for maintaining an approximation of the Hausdorff distance between two point sets in a constant dimension d , a standard problem in computational geometry. Our solution has an approximation factor of 1 + ε for any constant ε > 0 and expected update time O ( log ⁡ U log ⁡ log ⁡ n ) , where U is the universe size, and n is the number of the points. The result of the paper greatly improves over the previous exact method, which required O ( n 5 / 6 polylog n ) time and worked only in a semi-online setting. The model of computation is the word RAM model. [ABSTRACT FROM AUTHOR]

Abstract: Given a (master) set M of n points in d-dimensional Euclidean space, consider drawing a random subset that includes each point with an independent probability . How difficult is it to compute elementary statistics about the closest pair of points in such a subset? For instance, what is the probability that the distance between the closest pair of points in the random subset is no more than ℓ, for a given value ℓ? Or, can we preprocess the master set M such that given a query point q, we can efficiently estimate the expected distance from q to its nearest neighbor in the random subset? These basic computational geometry problems, whose complexity is quite well-understood in the deterministic setting, prove to be surprisingly hard in our stochastic setting. We obtain hardness results and approximation algorithms for stochastic problems of this kind. [Copyright &y& Elsevier]

We answer a basic data structuring question (e.g., raised by Dietz and Raman [1991]): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1,..., U} under an arbitrary sequence of n insertions and deletions, with O(log log U) expected query time and expected amortized update time, and O(n) space. The query bound is optimal in U for linear-space structures and improves previous near-O((log log U)²) methods. The same method solves a fundamental problem from computational geometry: point location in orthogonal planar subdivisions (where edges are vertical or horizontal). We obtain the first static data structure achieving O(log log U) worst-case query time and linear space. This result is again optimal in U for linearspace structures and improves the previous O((log log U)²) method by de Berg et al. [1995]. The same result also holds for higher-dimensional subdivisions that are orthogonal binary space partitions, and for certain nonorthogonal planar subdivisions such as triangulations without small angles. Many geometric applications follow, including improved query times for orthogonal range reporting for dimensions ≥ 3 on the RAM. Our key technique is an interesting new van-Emde-Boas-style recursion that alternates between two strategies, both quite simple. [ABSTRACT FROM AUTHOR]

We present three results related to dynamic convex hulls: A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line, with expected query and amortized update time O(log1+ε n) for an arbitrarily small constant ε > 0. This improves the previous bound of O(log3/2n). A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n + k) time with O(polylogn) expected amortized update time. A similar result holds for 3-dimensional orthogonal range reporting. For 3-dimensional halfspace range reporting, the query time increases to O(log² n/ log log n + k). A semi-online dynamic data structure for maintaining a set of n line segments in the plane, so that we can decide whether a query line segment lies completely above the lower envelope, with query time O(logn) and amortized update time O(nε). As a corollary, we can solve the following problem in O(n1+ε) time: given a triangulated terrain in 3-d of size n, identify all faces that are partially visible from a fixed viewpoint. [ABSTRACT FROM AUTHOR]

Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n). [ABSTRACT FROM AUTHOR]

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity ill an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain all understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in Õ(m2/3 amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7-13], which required fast matrix multiplication and had an update time of O(m0.94). The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, Õ (n2/3), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: O*(n9/10); for d-dimensional simplices: O* (n 1 - 1/d(2d+1) ); and for d-dimensional balls: O* (n1 - 1/d(d+1)(2d+3)). [ABSTRACT FROM AUTHOR]

Abstract: Given n axis-parallel boxes in a fixed dimension , how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee''s measure problem, can be solved in time by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time , where denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near , ignoring factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple. [Copyright &y& Elsevier]

Given a planar subdivision whose coordinates are integers bounded by U ⩽ 2w, we present a linear-space data structure that can answer point-location queries in O(min{lg n/ lg lg n, √lg U/ lg lgU}) time on the unit-cost random access machine (RAM) with word size w. This is the first result to beat the standard Θ(lg n) bound for infinite precision models. As a consequence, we obtain the first o(n lg n) (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word RAM, including: constructing the convex hull of a three-dimensional (3D) point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed. Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92). [ABSTRACT FROM AUTHOR]

Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph G = (V,E) and a subset of vertices S ⊆ V to support insertions/deletions in S and connectivity queries (are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using a combination of several simple ideas. Our method requires Õ(∣E∣4ω/(3ω+3)) = O(∣E∣0.94) amortized update time, and Õ(∣E∣1/3) query time, after Õ(∣E∣(5ω+1)/(3ω+3)) preprocessing time, where ? is the matrix multiplication exponent and Õ hides polylogarithmic factors. [ABSTRACT FROM AUTHOR]

Given n points in three dimensions, we show how to answer halfspace range reporting queries in O(log n + k) expected time for an output size k. Our data structure can be preprocessed in optimal O(n log n) expected time. We apply this result to obtain the first optimal randomized algorithm for the construction of the (≤k)-level in an arrangement of n planes in three dimensions. The algorithm runs in O(n log n+nk[SUP2]) expected time. Our techniques are based on random sampling. Applications in two dimensions include an improved data structure for "k nearest neighbors" queries and an algorithm that constructs the order-k Voronoi diagram in O(n log n+nk log k) expected time. [ABSTRACT FROM AUTHOR]

We design efficient data structures for dynamically maintaining a ham-sandwich cut of two point sets in the plane subject to insertions and deletions of points in either set. A ham-sandwich cut is a line that simultaneously bisects the cardinality of both point sets. For general point sets, our first data structure supports each operation in O(n1/3+ε) amortized time and O(n4/3+ε) space. Our second data structure performs faster when each point set decomposes into a small number k of subsets in convex position: it supports insertions and deletions in O(logn) time and ham-sandwich queries in O(klog4n) time. In addition, if each point set has convex peeling depth k , then we can maintain the decomposition automatically using O(klogn) time per insertion and deletion. Alternatively, we can view each convex point set as a convex polygon, and we show how to find a ham-sandwich cut that bisects the total areas or total perimeters of these polygons in O(klog4n) time plus the O((kb)polylog(kb)) time required to approximate the root of a polynomial of degree O(k) up to b bits of precision. We also show how to maintain a partition of the plane by two lines into four regions each containing a quarter of the total point count, area, or perimeter in polylogarithmic time., Engineering and Applied Sciences