Efficient computation of the discrete Voronoi diagram without the InCircle predicate

David Millman and Jack Snoeyink, UNC Chapel Hill

The Voronoi diagram of a set of n sites in the plane is a decomposition of the plane into regions with the same set of closest sites. The discrete Voronoi, also known as the distance transform, simply labels each point of a grid by the closest site or sites. This can be done in double precision by measuring the squared distance to each site, but it is more efficient to compute the Voronoi diagram and then locate the grid points. Liotta, Preparatta, & Tammassia suggested to look at the arithmetic precision required by geometric algorithms; they essentially showed that if you computed the Voronoi diagram, whose representation requires 5-fold precision, you could actually round it down to double precision without changing the closest site for any grid point. We compute their reduced Voronoi diagram directly using double precision, by randomized incremental construction in O(n log n log U) time, for a UxU grid. This opens the question of what other structures can be computed efficiently in reduced precision.

Close

Detecting Hotspots in Geographic Networks

Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günther Rote, Rodrigo I.Silveira, Bettina Speckmann, and Thomas Wolle

We study a point pattern detection problem on networks, motivated by geographical analysis tasks, such as crime hotspot detection. Given a network N (for example, a street, train, or highway network) together with a set of sites which are located on the network (for example, accident locations or crime scenes), we want to find a connected subnetwork F of N of small total length that contains many sites. That is, we are searching for a subnetwork F that spans a cluster of sites which are close with respect to the network distance.
We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with self-intersections at vertices, or a tree. Many of these variants are NP-hard, that is, polynomial-time solutions are very unlikely to exist. Hence we focus on exact algorithms for special cases and efficient algorithms for the general case under realistic input assumptions.

Close

Connect the Dot: Computing Feed-links with Minimum Dilation

Boris Aronov, Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, Bettina Speckmann

A feed-link is an artificial connection from a given location p to a real world network. It is most commonly added to an incomplete network to improve the results of network analysis, by making p part of the network. The feed-link has to be reasonable, hence we use the concept of dilation to determine the quality of a connection. We consider the following abstract problem: Given a simple polygon P with n vertices and a point p inside, determine a point q on P such that adding a feedlink pq minimizes the maximum dilation of any point on P. Here the dilation of a point r on P is the ratio of the shortest route from r over P and pq to p, to the Euclidean distance from r to p. We solve this problem in O(lambda_7(n) log n) time, where lambda_7(n) is the slightly superlinear maximum length of a Davenport-Schinzel sequence of order 7. We also show that for convex polygons, two feed-links are always sufficient and sometimes necessary to realize constant dilation, and that k feed-links lead to a dilation of 1+O(1/k). For (alpha,beta)-covered polygons, a constant number of feed-links suffices to realize constant dilation.

Close

Geometric Simultaneous Embeddings of a Graph and a Matching

Sergio Cabello, Marc van Kreveld, Giuseppe Liotta, Henk Meijer, Bettina Speckmann, and Kevin Verbeek

The geometric simultaneous embedding problem asks whether two planar graphs on the same set of vertices in the plane can be drawn using straight lines, such that each graph is plane. Geometric simultaneous embedding is a current topic in graph drawing and positive and negative results are known for various classes of graphs. So far only connected graphs have been considered. In this paper we present the first results for the setting where one of the graphs is a matching. In particular, we show that there exists a planar graph and a matching which do not admit a geometric simultaneous embedding. This generalizes the same result for a planar graph and a path. On the positive side, we describe algorithms that compute a geometric simultaneous embedding of a matching and a wheel, outerpath, or tree. Our proof for a matching and a tree sheds new light on a major open question: do a tree and a path always admit a geometric simultaneous embedding? Our drawing algorithms minimize the number of orientations used to draw the edges of the matching. Specifically, when embedding a matching and a tree, we can draw all matching edges horizontally. When embedding a matching and a wheel or an outerpath, we use only two orientations.

Close

Planning Short Paths with Clearance using Explicit Corridors

Roland Geraerts

A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character's path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time.
We introduce a data structure (i.e. the Explicit Corridor Map) which is an annotated Generalized Voronoi Diagram, and show how it can be computed efficiently by using the graphics card. Then we'll introduce algorithms for creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time.

Close

Computing Delaunay Triangulations from Simpler Structures

Kevin Buchin

Often the input data for an algorithm comes with some structure. Many point sets naturally exhibit spatial coherence because of the way they where captured, e.g., by a 3D scanner. The points might also already be stored in a hierarchical data structure. Even if the input points come unstructured, such structure can be added very fast, e.g., by building a quadtree of the points.
In this talk I present efficient algorithms for computing the Delaunay triangulation of a structured point set. The first algorithm is a simple and popular algorithm for computing the Delaunay triangulation from a space-filling curve order. I show that although its worst-case performance is poor, its performance in realistic settings is very good. The second algorithm computes the Delaunay triangulation from a quadtree of the points in linear time. I show two applications of this algorithm: computing Delaunay triangulations on a word RAM efficiently and computing Delaunay triangulations of imprecise points.

Close