Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set P of N points in 3-D, at SODA'14, Afshani and Tsakalidis designed an optimal O(N log₂N) time algorithm that constructs shallow cuttings for 3-D dominance ranges in internal memory. Even though shallow cuttings are used in the I/O-model to design space and query efficient range searching data structures, an efficient construction of them is not known till now. In this paper, we design an optimal-cost algorithm to construct shallow cuttings for 3-D dominance ranges. The number of I/Os performed by the algorithm is O (N/B log_{M/B}(N/B)), where B is the block size and M is the memory size. As two applications of the optimal-cost construction algorithm, we design fast algorithms for offline 3-D dominance reporting and offline 3-D approximate dominance counting. We believe that our algorithm will find further applications in offline 3-D range searching problems and in improving construction cost of data structures for 3-D range searching problems.

In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to RLIS is a sequence $S$ of $n$ real numbers and a collection $Q$ of $m$ query ranges, and for each query in $Q$, the goal is to report the LIS of the sequence $S$ restricted to that query. Our two main results are for the following generalizations of the RLIS problem. 2D range queries: In this variant of the RLIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide a randomized algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$, where $k$ is the cumulative length of the $m$ output subsequences. This improves on the elementary $O(mn)$-time algorithm when $m$ is at least $n^{1/2}$. Previously, the only known result breaking the quadratic barrier was due to Tiskin [SODA'10], which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length). Colored sequences: In this variant of the RLIS problem, each element in $S$ is colored, and for each query in $Q$, the goal is to report a monochromatic LIS contained in the sequence $S$ restricted to that query. For 2D queries, we provide a randomized algorithm for this colored version with running time $\tilde{O}(m n^{2/3} + n^{5/3}) + O(k)$. Moreover, for 1D queries, we provide an improved algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$. Thus, we again improve on the elementary $O(mn)$-time algorithm. Additionally, assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, we prove that the running time for 1D queries is essentially tight for combinatorial algorithms.

In this work we revisit the maximum range sum (MaxRS) problem which is well studied by the database and the computational geometry communities. The input is a set P of n weighted points in R d and a geometric range Q (typically either an axis-aligned d -box or a d -ball). The goal is to design a fast algorithm to place Q in R d so that the total weight of the points of P inside Q is maximized. We consider three natural variations of the MaxRS problem: In the dynamic MaxRS problem, points are inserted and deleted, and the goal is to efficiently update the placement of a d -ball. In R d we present a randomized (1/2 - ε)-approximation algorithm with update time O ε (log n). The approximation factor holds with high probability. To the best of our knowledge, this problem was not studied before in the literature. In the batched MaxRS problem in R 1 , along with the points in P we are given m intervals of different lengths. The goal is to solve the MaxRS problem for each interval. We establish a conditional lower bound of Ω(mn) time for this problem, assuming the hardness of (min,+)-convolution problem. Interestingly, this implies that the trivial upper bound of O(mn log n) for batched MaxRS in R 2 is almost-tight. A similar lower bound is established for a related problem of batched smallest k -enclosing interval. In the colored MaxRS problem in R d , each point in P is assigned a color from {1,2,...,m} and the goal is to find the placement of a d -ball Q that maximizes the number of uniquely colored points in P ∩ Q. Prior work on this problem was limited to axis-aligned rectangle Q in R 2 . We obtain two new results for d -balls. The first result is a randomized (1/2 - ε)-approximation algorithm with running time O ε (n log n). Interestingly, the exponential dependence of log n on d is avoided in the running time. The second result improves upon the first result in R 2 by providing a (1-ε)-approximation algorithm with expected running time O_ε(n log n). The approximation factor holds with high probability for both results. Our algorithms are obtained via two general techniques which we believe will be useful for solving other variants of MaxRS. The first technique provides a (1/2 - ε)-approximation guarantee. The analysis relies on a volume argument involving d -balls and a randomized game. The second technique provides a (1-ε)-approximation guarantee and works in two phases. In the first phase, we design an exact output-sensitive algorithm, and in the second phase, we speed up the exact algorithm by random sampling on colors.

The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform machine scheduling. For different machine speeds, LPT was first considered by Gonzalez et al (SIAM J. Computing, 1977). Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take $O(mn)$ time, where $m$ is the number of machines and $n$ is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT. Specifically, the running time is $O((n+m)(\log^2{m}+\log{n}))$. Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope of lines, which has been well studied in the computational geometry community. Our second contribution is to analyze the performance of LPT for the Drones Warehouse Problem (DWP), which is a natural generalization of the uniform machine scheduling problem motivated by drone-based parcel delivery from a warehouse. In this problem, a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it, and returns to the warehouse (where it can also get charged). The speeds and battery lives of the drones could be different, and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of $ϕ$, where $ϕ\approx 1.62$ is the golden ratio.

Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), $m$ sets (resp.~$n$ points) are give $n$ points (resp.~$m$ sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution. For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight $O(\log n)$-competitive algorithm. In the same setting for hitting set, we provide a tight $O(\log N)$-competitive algorithm, assuming that all points have integral coordinates in $[0,N)^{2}$. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems). For both dynamic set cover and hitting set with $d$-dimensional hyperrectangles, we obtain $(\log m)^{O(d)}$-approximation algorithms with $(\log m)^{O(d)}$ worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an \emph{extended quad-tree }approach and a \emph{frequency reduction} technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.

In the orthogonal range reporting problem we must pre-process a set P of multi-dimensional points, so that for any axis-parallel query rectangle q all points from q ∩ P can be reported efficiently. In this paper we study the query complexity of multi-dimensional orthogonal range reporting in the pointer machine model. We present a data structure that answers four-dimensional orthogonal range reporting queries in almost-optimal time O(log n log log n + k) and uses O(n log4 n) space, where n is the number of points in P and k is the number of points in q ∩ P. This is the first data structure with nearly-linear space usage that achieves almost-optimal query time in 4d. This result can be immediately generalized to d ≥ 4 dimensions: we show that there is a data structure supporting d-dimensional range reporting queries in time O(logd-3 n log log n + k) for any constant d ≥ 4. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.03161

In a geometric intersection graph, given a collection of n geometric objects as input, each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. In this work, we present a somewhat surprising result: a polynomial time algorithm for max cut on laminar geometric intersection graphs. In a laminar geometric intersection graph, if two objects intersect, then one of them will completely lie inside the other. To the best of our knowledge, for max cut this is the first class of (non-trivial) geometric intersection graphs with an exact solution in polynomial time. Our algorithm uses a simple greedy strategy. However, proving its correctness requires non-trivial ideas. Next, we design almost-linear time algorithms (in terms of n) for laminar axis-aligned boxes by combining the properties of laminar objects with vertical ray shooting data structures. Note that the edge-set of the graph is not explicitly given as input; only the n geometric objects are given as input.

A reporting query returns the objects satisfying a predicate q from an input set. In prioritized reporting , each object carries a real-valued weight (which can be query dependent), and a query returns the objects that satisfy q and have weights at least a threshold τ. A top- k query finds, among all the objects satisfying q , the k ones of the largest weights; a max query is a special instance with k = 1. We want to design data structures of small space to support queries (and possibly updates) efficiently. Previous work has shown that a top- k structure can also support max and prioritized queries with no performance deterioration. This article explores the opposite direction: do prioritized queries, possibly combined with max queries, imply top- k search? Subject to mild conditions, we provide affirmative answers with two reduction techniques. The first converts a prioritized structure into a static top- k structure with the same space complexity and only a logarithmic blowup in query time. If a max structure is available in addition, our second reduction yields a top- k structure with no degradation in expected performance (this holds for the space, query, and update complexities). Our techniques significantly simplify the design of top- k structures because structures for max and prioritized queries are often easier to obtain. We demonstrate this by developing top- k structures for interval stabbing, 3D dominance, halfspace reporting, linear ranking, and L ∞ nearest neighbor search in the RAM and the external memory computation models.

This paper studies a multi-armed bandit (MAB) version of the range-searching problem. In its basic form, range searching considers as input a set of points (on the real line) and a collection of (real) intervals. Here, with each specified point, we have an associated weight, and the problem objective is to find a maximum-weight point within every given interval. The current work addresses range searching with stochastic weights: each point corresponds to an arm (that admits sample access) and the point's weight is the (unknown) mean of the underlying distribution. In this MAB setup, we develop sample-efficient algorithms that find, with high probability, near-optimal arms within the given intervals, i.e., we obtain PAC (probably approximately correct) guarantees. We also provide an algorithm for a generalization wherein the weight of each point is a multi-dimensional vector. The sample complexities of our algorithms depend, in particular, on the size of the {optimal hitting set} of the given intervals. Finally, we establish lower bounds proving that the obtained sample complexities are essentially tight. Our results highlight the significance of geometric constructs (specifically, hitting sets) in our MAB setting.

Consider a set $$P\subseteq \mathbb {R}^d$$ of n points, and a convex body $$C$$ provided via a separation oracle. The task at hand is to decide for each point of $$P$$ if it is in $$C$$ using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using queries, where is the size of the largest subset of points of $$P$$ in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using oracle queries, where is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if $$C$$ contains all points of $$P$$ . As an application of the above, we show that the discrete geometric median of a point set P in $$\mathbb {R}^2$$ can be computed in expected time.

We consider a range-search variant of the closest-pair problem. Let Gamma be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.

Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.

In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. -We give the first linear-space data structure that supports 3-d point location queries on $n$ disjoint axis-aligned boxes with optimal $O\left( \log n\right)$ query time in the (arithmetic) pointer machine model. This improves the previous $O\left( \log^{3/2} n \right)$ bound of Rahul [SODA 2015]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time. -We give the first linear-space data structure that supports 3-d $4$-sided and $5$-sided rectangle stabbing queries in optimal $O(\log_wn+k)$ time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-$k$ rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing. For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant of Alstrup, Brodal, and Rauhe's grid-based recursive technique (FOCS 2000), combined with a number of new ideas.

Let D be a set of n elements each associated with a real-valued weight, and Q be the set of all possible predicates allowed on those elements. Given a predicate in Q and integer k, a top-k query returns the k elements with the largest weights among the elements of D satisfying q. The corresponding data structure problem aims to store D in small space to allow every query to be answered efficiently. It is already known that, before settling the problem, one must be able to solve two degenerated accompanying problems: (i) prioritized reporting: given a predicate q ∈ Q and a real value τ, return all the elements of D satisfying q and having weights at least τ (ii) max reporting: top-k queries with k fixed to 1.

Orthogonal range reporting (ORR) is a classic problem in computational geometry and databases, where the objective is to preprocess a set P of points in R2 such that, given an axis-parallel rectangle q, all the points in P ∩ Q can be reported efficiently. This paper studies a natural variant of the problem called top-k ORR, where each point p ∈ P carries a weight w(p) ∈R;. Besides q, a query also specifies an integer k ∈ [1, |P|], and needs to report the k points in q ∩ P with the largest weights. We present optimal or near-optimal structures for solving the top-k ORR problem in the pointer machine and external memory models. As a side product, our structures give new space-query tradeoff for the orthogonal range max problem, which is a special case of top-k ORR with k = 1.

In this paper, new results for two fundamental problems in the field of computational geometry are presented: orthogonal point enclosure query (OPEQ) in ℝ3 and point location in orthogonal subdivisions in ℝ3. All the results are in the pointer machine model of computation.

In a top-k Geometric Intersection Query (top-k GIQ) problem, a set of n weighted, geometric objects in Rd is to be preprocessed into a compact data structure so that for any query geometric object, q, and integer k > 0, the k largest-weight objects intersected by q can be reported efficiently. While the top-k problem has been studied extensively for non-geometric problems (e.g., recommender systems), the geometric version has received little attention. This paper gives a general technique to solve any top-k GIQ problem efficiently. The technique relies only on the availability of an efficient solution for the underlying (non-top-k) GIQ problem, which is often the case. Using this, asymptotically efficient solutions are derived for several top-k GIQ problems, including top-k orthogonal and circular range search, point enclosure search, halfspace range search, etc. Implementations of some of these solutions, using practical data structures, show that they are quite efficient in practice. This paper also does a formal investigation of the hardness of the top-k GIQ problem, which reveals interesting connections between the top-k GIQ problem and the underlying (non-top-k) GIQ problem.

Let S be a set of n points in Rd where each point has t ≥ 1 real-valued attributes called features. A range-skyline query on S takes as input a query box q ε Rd and returns the skyline of the points of q ∩ S, computed w.r.t. their features (not their coordinates in Rd). Efficient algorithms are given for computing range-skylines and a related hardness result is established.