We present a number of new results on one the most extensively studied topics in computational geometry, orthogonal range searching. All our are standard word RAM model: two data structures for 2-d emptiness. The first achieves O(n lg n) space and O(lg query time, assuming that n given points rank space. This improves previous by Alstrup, Brodal, Rauhe (FOCS'00), with lgε or O(lg2lg time. Our second structure uses O(n) answers queries O(lgε best O(n)-space structure, due to Nekrich...

In the first part of paper, we reexamine all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n3/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to best result possible without using fast matrix multiplication, modulo few log n factors.

We present a collection of new results on problems related to 3SUM, including: The first truly subquadratic algorithm for computing the (min,+) convolution monotone increasing sequences with integer values bounded by O(n), solving 3SUM sets in 2D coordinates and preprocessing binary string histogram indexing (also called jumbled indexing).

We present the first optimal algorithm to compute maximum Tukey depth (also known as location or halfspace depth) for a non-degenerate point set in plane. The is randomized and requires O(n log n) expected time n data points. In higher fiexed dimension d ≥ 3, bound O(nd-1), which probably well. result obtained using an interesting variant of author's optimization technique, capable solving implicit linear-programming-type problems; some other applications this technique are briefly mentioned.

In the first part of paper, we reexamine all-pairs shortest path (APSP) problem and present a new algorithm with running time $O(n^3\log^3\log n/\log^2n)$, which improves all known algorithms for general real-weighted dense graphs. second use fast matrix multiplication to obtain truly subcubic APSP large class "geometrically weighted" graphs, where weight an edge is function coordinates its vertices. For example, graphs embedded in Euclidean space constant dimension d, bound near...

The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case. We take approach of exploiting structure achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property as shallow cell complexity (SCC). Roughly speaking, instance has low SCC if any column-induced submatrix corresponding element-set incidence matrix few distinct...

We present a new algorithm for classic problem in computational geometry, Klee's measure problem: given set of n axis-parallel boxes d-dimensional space, compute the volume union boxes. The runs O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d/2</sup> ) time any constant d ≥ 3. Although it improves previous best by "just" an iterated logarithmic factor, real surprise lies simplicity algorithm. also show that is theoretically possible to...

This paper considers the planar Euclidean two-center problem: given a n-point set S, find two congruent circular disks of smallest radius covering S. The main result is deterministic algorithm with running time O(nlog2nlog2logn), improving previous O(nlog9n) bound Sharir and almost matching randomized O(nlog2n) Eppstein. If point in intersection given, then we can solve problem O(nlogn) high probability.

We revisit one of the most fundamental classes data structure problems in computational geometry: range searching. Back SoCG'92, Matousek gave a partition tree method for d-dimensional simplex searching achieving O(n) space and O(n1-1/d) query time. Although this is generally believed to be optimal, it complicated requires O(n1+ε) preprocessing time any fixed ε>0. An earlier by (SoCG'91) O(n log n) but O(n1-1/d logO(1)n) give new that achieves simultaneously time, space, with high...

We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. show that n points 3-d can be stored linear-space data structure so all k inside query reported O(log + k) time. The built O(n log n) expected previous methods with time required superlinear (O(n n)) space.We also mention consequences, for example, higher dimensions and external-memory structures. As an aside, we partially answer another open question concerning...

We present a fully dynamic randomized data structure that can answer queries about the convex hull of set n points in three dimensions, where insertions take O (log 3 ) expected amortized time, deletions 6 and extreme-point 2 worst-case time. This is first method guarantees polylogarithmic update query cost for arbitrary sequences deletions, improves previous ( ϵ )-time by Agarwal Matoušek decade ago. As consequence, we obtain similar results nearest neighbor two dimensions improved numerous...

We give an O(n √lg n)-time algorithm for counting the number of inversions in a permutation on n elements. This improves long-standing previous bound lg n/ n) that followed from Dietz's data structure [WADS'89], and answers question Andersson Petersson [SODA'95]. As result is known to be optimal related dynamic rank problem, our demonstrates significant improvement offline setting.Our new technique quite simple: we perform vertical partitioning trie (akin van Emde Boas trees), use ideas...

We design new polynomials for representing threshold functions in three different regimes: probabilistic of low degree, which need far less randomness than previous constructions, polynomial (PTFs) with "nice" behavior and degree almost as the polynomials, a notion PTFs where we combine above techniques to achieve even lower similar behavior. Utilizing these faster algorithms variety problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red blue points d-dimensional space d =...

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? present (partially) persistent structure that supports predecessor search in set of integers {1, ..., U } under an arbitrary sequence n insertions deletions, with O (log log ) expected query time amortized update time, ( space. The bound is optimal for linear-space structures improves previous near- ((log 2...

We show how to solve all-pairs shortest paths on n nodes in deterministic n3/2Ω([EQUATION]) time, and count the pairs of orthogonal vectors among 0-1 d = clogn dimensions n2−1/O(logc) time. These running times essentially match best known randomized algorithms (Williams, STOC'14) (Abboud, Williams, Yu, SODA 2015) respectively, ability was open even for algorithms. By reductions, these two results yield faster many other problems. Our techniques can also be used deterministically k-SAT...