International Journal of Computational Geometry & Applications

We solve several fundamental geometric problems under a new streaming model recently proposed by Ruhl et al.^2,15 In this model, in one pass the input stream can be scanned to generate an output stream or be sorted based on a user-defined comparator; all intermediate streams must be of size O(n). We obtain the following geometric results for any fixed constant ϵ > 0:

• We can construct 2D convex hulls in O(1) passes with O(n^ϵ) extra space.

• We can construct 3D convex hulls in O(1) expected number of passes with O(n^ϵ) extra space.

• We can construct a triangulation of a simple polygon in O(1) expected number of passes with O(n^ϵ) extra space, where n is the number of vertices on the polygon.

• We can report all k intersections of a set of 2D line segments in O(1) passes with O(n^ϵ) extra space, if an intermediate stream of size O(n + k) is allowed.

We also consider a weaker model, where we do not have the sorting primitive but are allowed to choose a scan direction for every scan pass. Here we can construct a 2D convex hull from an x-ordered point set in O(1) passes with O(n^ϵ) extra space.

Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects. We investigate spatio-temporal movement patterns in large tracking data sets, i.e. in large sets of polygonal paths. Specifically, we study so-called 'popular places', that is, regions that are visited by many entities.

Given a set of polygonal paths with a total of vertices, we look at the problem of computing such popular places in two different settings. For the discrete model, where only the vertices of the polygonal paths are considered, we propose an algorithm; and for the continuous model, where also the straight line segments between the vertices of a polygonal path are considered, we develop an algorithm. We also present lower bounds and hardness results.

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network G_S with minimum size so that for any pair of points in S, there exists a path in G_S with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n²log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S.

Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log³ n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a (1 - ϵ)-approximation to the dilation of every path C \{e}, for all edges e of C, can be computed in O(n log n) total time.

Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle.

In this paper we consider a natural extension of this problem: Given in addition a Steiner pointp, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.