Sparse geometric graphs with small dilation

Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

Covering point sets with two disjoint disks or squares

We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks C_R and C_B with disjoint interiors such that the number of red points covered by C_R plus the number of blue points covered by C_B is maximized. We give an algorithm to solve this problem in O(n^8/3log²n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares S_R and S_B instead of unit disks can be solved in O(nlogn) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n³logn) time.     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.     

Computing the Fréchet distance between piecewise smooth curves

We consider the Fréchet distance between two curves which are given as a sequence of m+n curved pieces. If these pieces are sufficiently well-behaved, we can compute the Fréchet distance in O(mnlog(mn)) time. The decision version of the problem can be solved in O(mn) time. The results are based on an analysis of the possible intersection patterns between circles and arcs of bounded curvature.     

Computing homotopic shortest paths efficiently

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(k_out+k_inlogn+n(logn)^1+ε). Here k_in is the number of edges in all the paths of Π, and k_out is the number of edges in the output paths.     

A quadratic distance bound on sliding between crossing-free spanning trees

Let S be a set of n points in the plane and let be the set of all crossing-free spanning trees of S. We show that it is possible to transform any two trees in into each other by O(n²) local and constant-size edge slide operations. Previously no polynomial upper bound for this task was known, but in [O. Aichholzer, F. Aurenhammer, F. Hurtado, Sequences of spanning trees and a fixed tree theorem, Comput. Geom.: Theory Appl. 21 (1–2) (2002) 3–20] a bound of O(n²logn) operations was conjectured.     

On finding widest empty curved corridors

An -siphon of width w is the locus of points in the plane that are at the same distance w from a 1-corner polygonal chain C such that is the interior angle of C. Given a set P of n points in the plane and a fixed angle , we want to compute the widest empty -siphon that splits P into two non-empty sets. We present an efficient O(nlog³n)-time algorithm for computing the widest oriented -siphon through P such that the orientation of a half-line of C is known. We also propose an O(n³log²n)-time algorithm for the widest arbitrarily-oriented version and an Θ(nlogn)-time algorithm for the widest arbitrarily-oriented -siphon anchored at a given point.     

The minimum-area spanning tree problem

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set of n points in the plane, find a spanning tree of of minimum “area”, where the area of a spanning tree is the area of the union of the n−1 disks whose diameters are the edges in . We prove that the Euclidean minimum spanning tree of is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.     

On the Fermat–Weber center of a convex object

We show that for any convex object Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is at least Δ(Q)/7, where Δ(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Δ(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat–Weber center of a convex polygon Q.     

Adaptive sampling for geometric problems over data streams

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. This paper focuses on the problem of summarizing such geometric data streams using limited storage so that many natural geometric queries can be answered faithfully. Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset, or track the extent of the dataset in any given direction. One can also pose queries over multiple streams: for instance, track the minimum distance between the convex hulls of two data streams, report when datasets A and B are no longer linearly separable, or report when points of data stream A become completely surrounded by points of data stream B, etc. These queries are easily extended to more than two streams.

In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r+1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r²), where D is the diameter of the sample set. The amortized time for processing each point in the stream is O(logr). Using the sample convex hull, all the queries mentioned above can be answered approximately in either O(logr) or O(r) time.     

Countable choice and compactness

We work in set-theory without choice ZF. Denoting by the countable axiom of choice, we show in that the closed unit ball of a uniformly convex Banach space is compact in the convex topology (an alternative to the weak topology in ZF). We prove that this ball is (closely) convex-compact in the convex topology. Given a set I, a real number p1 (respectively p=0), and some closed subset F of [0,1]^I which is a bounded subset of ℓ^p(I), we show that (respectively DC, the axiom of Dependent Choices) implies the compactness of F.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

Fractal sets determined by dilation-stable processes

Let be a dilation-stable process on . We determine a Hausdorff measure function (a) such that the fractal set X[0,1]={X(t):0t1} has positive finite -measure. We also investigate the packing measure of X[0,1].     

On periodic radical groups in which permutability is a transitive relation

A group G is said to be a -group if permutability is a transitive relation in the set of all subgroups of G. Our purpose in this paper is to study -groups in the class of periodic radical groups satisfying min-p for all primes p.     

Space-efficient geometric divide-and-conquer algorithms

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in time using extra memory given inputs of size n for the closest pair problem and a randomized solution running in expected time and using extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in time using extra space where n is the number of horizontal and vertical line segments and k is the number of intersections.     

Minimum weight pseudo-triangulations

We consider the problem of computing a minimum weight pseudo-triangulation of a set of n points in the plane. We first present an -time algorithm that produces a pseudo-triangulation of weight which is shown to be asymptotically worst-case optimal, i.e., there exists a point set for which every pseudo-triangulation has weight , where is the weight of a minimum weight spanning tree of . We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.     

Graph drawings with few slopes

The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least . This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most . Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper, planar drawings of graphs with few slopes are also considered.     

Farthest-point queries with geometric and combinatorial constraints

In this paper we discuss farthest-point problems in which a set or sequence S of n points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in O(log²n) time. Our data structure needs O(nlogn) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.     

Augmenting the connectivity of geometric graphs

Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, additional edges are required in some cases and that additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to and , respectively.