7th Dutch Computational Geometry Day

Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures

Constantinos Tsirogiannis (TU Eindhoven)

Watersheds, river networks, Morse-Smale complexes, and other flow-related structures on terrains are usually defined in terms of paths of steepest descent (or ascent). Unfortunately, a single path of steepest descent on a polyhedral terrain T with n vertices can have Θ(n²) complexity, since there can be Θ(n) triangles that are each crossed Θ(n) times. The watershed of a point p—the set of points on T whose path of steepest descent reaches p—can even have complexity Θ(n³). This makes the explicit computation of these structures time-consuming.

We present a technique for tracing implicitly a path of steepest descent on T, or even a collection of n such paths, in O(n log n) time. Based on this technique, we present O(n log n) time algorithms for the following problems:

• computing for each local minimum of T the set of terrain triangles that lie completely in the watershed of p;

• computing the surface network of T, which is the graph whose nodes are the critical points (local minima and maxima, and saddle points) and whose arcs connect the saddle points to local extrema through paths of steepest descent or ascent.

We also present an O(n²) time algorithm that computes for each local minimum of T the exact surface area of its watershed.

This joint work with Mark de Berg and Herman Haverkort.

Embedding Stacked Polytopes on a Polynomial-Size Grid

André Schulz (WWU Münster)

We show how to realize a stacked 3D polytope (formed by repeatedly stacking a tetrahedron onto a triangular face) by a strictly convex embedding with its n vertices on an integer grid of size O(n⁴)× O(n⁴) × O(n²⁴). We use a perturbation technique to construct an integral 2D embedding that lifts to a small 3D polytope, all in linear time. This result solves a question posed by Günter Ziegler, and is the first nontrivial subexponential upper bound on the long-standing open question of the grid size necessary to embed arbitrary convex polyhedra, that is, about efficient versions of Steinitz's 1916 theorem. An immediate consequence of our result is that O(log n)-bit coordinates suffice for a greedy routing strategy in planar 3-trees.

Computing Homotopic Line Simplification in a Plane

Mohammad Abam (Dortmund University)

We study a variant of the line-simplification problem where we are given a polygonal path P = p₁, p₂, …, p_n and a set S of m point obstacles in a plane, and the goal is to find the optimal homotopic simplification, that is, a minimum subsequence Q = q₁, q₂, …, q_k (q₁ = p₁ and q_k = p_n) of P defining a polygonal path which approximates P within the given error ε and is homotopic to P. We present a general method running in time O(n(m + n) log nm) for identifying every shortcut p_ip_j that is homotopic to the sub-path p_i, …, p_j of P, called a homotopic shortcut. In the case of x-monotone paths we propose an efficient and simple method to compute all homotopic shortcuts in O(m log nm + n log n log nm + k) time where k is the number of homotopic shortcuts. This improves the best known algorithm running in O(n(n+m) log n) time. Under any desired measure, both these methods can be simply combined with the Imai and Iri' framework to obtain the optimal homotopic simplification. We also present the first output-sensitive line-simplification algorithm, which might be of independent interest, for the Hausdorff distance under the uniform metric for x-monotone paths that runs in O(n log² n + k) where k is the number of all shortcuts whose errors are at most ε.

Universal Pointsets for 2-coloured Trees

Mereke van Garderen (Roosevelt Academy)

Let R and B be two sets of distinct points such that the points of R are coloured red and the points of B are coloured blue. Let G be a family of planar graphs such that for each graph in the family |R| vertices are red and |B| vertices are blue. The set R ∪ B is a universal pointset for G if every graph G ∈ G has a straight-line planar drawing such that the blue vertices of G are mapped to the points of B and the red vertices of G are mapped to the points of R. In this paper we describe universal pointsets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.

Joint work with Giuseppe Liotta and Henk Meijer

Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux

Matias Korman (Université Libre de Bruxelles)

We consider the optimization problem of finding k nonintersecting rectangles and tableaux in n × n pixel plane where each pixel has a real valued weight. We discuss existence of efficient algorithms if a corner point of each rectangle/tableau is specified.

Joint work with Shinya Anzai, Jinhee Chun, Ryosei Kasai and Takeshi Tokuyama

Go with the Flow: The Direction-Based Frechet Distance of Polygonal Curves

Atlas Cook IV (TU Eindhoven)

We introduce a new similarity measure called the direction-based integral Frechet distance. The direction-based integral Frechet distance is defined for directed curves in R^d. Like the standard Frechet distance, this measure optimizes over all parameterizations for a pair of curves. Unlike the Frechet distance, the measure is based on directional differences between curve segments rather than on positional differences between points on the curves. This paper describes an exact algorithm that computes the direction-based integral Frechet distance by optimizing over the integral of the directional differences. The measure is invariant under translations and scalings and can be used to compute partial matches. Speed limits can also be used to constrain the slope of all legal parameterizations for the direction-based integral Frechet distance, and we provide an efficient approximation algorithm for this scenario. We have also used experimental analysis to compare the strengths and weaknesses of the direction-based integral Frechet distance with the traditional integral Fréchet distance. The implementation is available as an online applet at http://www.win.tue.nl/~acook/applets/directionfrechet/. This is joint work with Mark de Berg.

Lombardi Drawings of Graphs

David Eppstein (UC Irvine)

Mark Lombardi was a fine artist whose art depicted the social networks underlying international criminal, political, and financial conspiracies. In honor of Lombardi, we define a Lombardi drawing to be a drawing of a graph in which the edges are drawn as circular arcs and at each vertex they are equally spaced around the vertex so as to achieve the best possible angular resolution. We describe algorithms for constructing Lombardi drawings of regular graphs, 2-degenerate graphs, graphs with rotational symmetry, and several types of planar graphs, and present the results from implementations of some of our algorithms.

Fréhet Distance of Surfaces: Some Simple Hard Cases

We show that it is NP-hard to decide the Fréchet distance between (i) non-intersecting polygons with holes embedded in the plane, (ii) 2d terrains, and (iii) self-intersecting simple polygons in 2d, which can be unfolded in 3d. The only previously known NP-hardness result for 2d surfaces was based on self-intersecting polygons with an unfolding in 4d. In contrast to this old result, our NP-hardness reductions are substantially simpler. As a positive result we show that the Fréchet distance between polygons with one hole can be computed in polynomial time.

The Geodesic Diameter of Polygonal Domains

Yoshio Okamoto (Japan Advanced Institute of Science and Technology)

This work studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h=0), it is known that the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time. For general polygonal domains with h≥1, however, no algorithm for computing the geodesic diameter was known prior to this work. In this work, we present the first algorithm that computes the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n⁷ (log n + h)). Among other results, we show the following geometric observation: the geodesic diameter can be determined by two points in its interior. In such a case, there are at least five shortest paths between the points.

Joint work with Sang Won Bae and Matias Korman.

An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria

Anne Driemel (Utrecht University)

We address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, and curviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented. This is joint work with Maike Buchin, Marc van Kreveld and Vera Sacristán.

Area-Preserving Subdivision Schematization

Wouter Meulemans (TU Eindhoven)

We describe an area-preserving subdivision schematization algorithm: the area of each region in the input equals the area of the corresponding region in the output. Our schematization is axis-aligned, the final output is a rectilinear subdivision. We first describe how to convert a given subdivision into an area-equivalent rectilinear subdivision. Then we define two area-preserving contraction operations and prove that at least one of these operations can always be applied to any given simple rectilinear polygon. We extend this approach to subdivisions and showcase experimental results. Finally, we give examples for standard distance metrics (symmetric difference, Hausdorff- and Fréchet-distance) that show that better schematizations might result in worse shapes.