Search

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: … These represent the best time bounds known for the problem for all m << n1.376.We also obtain a similar type of result for the diameter problem for unweighted directed graphs. [ABSTRACT FROM AUTHOR]

We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n2 + k) time for the three-dimensional case, where k is the number of these simplices. As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n2 + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections. [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]

We study a bichromatic version of the well-known k-set problem: given two sets R and B of points of total size n and an integer k, how many subsets of the form (R ∩h)∪(B \h) can have size exactly k over all halfspaces h? In the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the k-level in an arrangement of n halfspaces. Disproving an earlier conjecture by Linhart [1993], we present the first nontrivial upper bound for all k ⪡ n in two dimensions: O(nk1/3 +n5/6-ϵk2/3+2ϵ +k²) for any fixed ϵ > 0. In three dimensions, we obtain the bound O(nk3/2 +n0.5034k2.4932 +k³). Incidentally, this also implies a new upper bound for the original k-set problem in four dimensions: O(n²k3/2 + n1.5034k2.4932 + nk³), which improves the best previous result for all k ⪡ n0.923. Extensions to other cases, such as arrangements of disks, are also discussed. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n³ log³ log n/ log² n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where logω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-logω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+logω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [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]