DCGD 2010
2015 (UU) · 2013 (TU/e) · 2012 (UU) · 2010 (TU/e) · 2009 (UU) · 2008 (TU/e) · 2007 (UU) · 2006 (TU/e) · 2005 (UU) · 2004 (TU/e)
7th Dutch Computational Geometry Day
Date: 
11 November 2010 
Location: 
TU Eindhoven, “Hoofdgebouw” (HG
on map below), 5th floor, room 5.95 
Registration: 
Send email to Kevin
Buchin, stating name, affiliation, if you will join us for
dinner, and any dietary restrictions you may have. 
Sponsor: 
This meeting is kindly supported by the mathematics cluster
DIAMANT.

Program
Time  Speaker  Title 
10:15  10:30  Coffee 
10:30  10:50  Constantinos Tsirogiannis  Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures [Abstract] 
10:50  11:10  Anne Driemel  An Algorithmic Framework for Segmenting Trajectories based on SpatioTemporal Criteria [Abstract] 
11:10  11:30  André Schulz  Embedding Stacked Polytopes on a PolynomialSize Grid [Abstract] 
11:30  11:45  Minibreak 
11:45  12:05  Matias Korman  Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux [Abstract] 
12:05  12:25  Wouter Meulemans  AreaPreserving Subdivision Schematization [Abstract] 
12:25  12:45  Mereke van Garderen  Universal Pointsets for 2coloured Trees [Abstract] 
12:45  14:00  Lunch at 8th floor Lounge, room 8.39 
14:00  15:00  David Eppstein (invited speaker) 
Lombardi Drawings of Graphs [Abstract] 
15:00  15:30  Coffee break 
15:30  15:50  Atlas Cook IV  Go with the Flow: The DirectionBased Frechet Distance of Polygonal Curves [Abstract] 
15:50  16:10  Mohammad Abam  Computing Homotopic Line Simplification in a Plane [Abstract] 
16:10  16:25  Minibreak 
16:25  16:45  Yoshio Okamoto  The Geodesic Diameter of Polygonal Domains [Abstract] 
16:45  17:05  Maike Buchin  Fréchet Distance of Surfaces: Some Simple Hard Cases [Abstract] 
17:05  18:00  “Borrel” 

25 minute walk to Kerkstraat 40 
18:30  Dinner at Greek restaurant “Papadopoulos” 
Campus map
Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures
Constantinos Tsirogiannis (TU Eindhoven)
Watersheds, river networks, MorseSmale complexes, and other flowrelated 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^{2}) 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^{3}). This makes the explicit computation of these structures
timeconsuming.
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^{2}) 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.
Close
Embedding Stacked Polytopes on a PolynomialSize 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^{4})× O(n^{4}) × O(n^{24}).
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 longstanding
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 3trees.
Close
Computing Homotopic Line Simplification in a Plane
Mohammad Abam (Dortmund University)
We study a variant of the linesimplification problem where we are
given a polygonal path P = p_{1}, p_{2}, …,
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_{1},
q_{2}, …, q_{k} (q_{1} =
p_{1} 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_{i}p_{j} that is homotopic to the
subpath p_{i}, …, p_{j}
of P, called a homotopic shortcut. In the case
of xmonotone 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 outputsensitive
linesimplification algorithm, which might be of independent interest,
for the Hausdorff distance under the uniform metric
for xmonotone paths that runs
in O(n log^{2} n + k) where k is
the number of all shortcuts whose errors are at
most ε.
Close
Universal Pointsets for 2coloured 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 straightline 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 2coloured trees
and show applications of these results to the coloured
simultaneous geometric embeddability problem.
Joint work with Giuseppe Liotta and Henk Meijer
Close
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
Close
Go with the Flow: The DirectionBased Frechet Distance of Polygonal Curves
Atlas Cook IV (TU Eindhoven)
We introduce a new similarity measure called the directionbased integral Frechet distance.
The directionbased 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 directionbased 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 directionbased 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 directionbased 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.
Close
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, 2degenerate
graphs, graphs with rotational symmetry, and several types of planar
graphs, and present the results from implementations of some of our
algorithms.
Close
Fréhet Distance of Surfaces: Some Simple Hard Cases
We show that it is NPhard to decide the Fréchet distance
between (i) nonintersecting polygons with holes embedded in the
plane, (ii) 2d terrains, and (iii) selfintersecting simple polygons
in 2d, which can be unfolded in 3d. The only previously known
NPhardness result for 2d surfaces was based on selfintersecting
polygons with an unfolding in 4d. In contrast to this old result, our
NPhardness 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.
Close
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
worstcase time O(n^{7.73}) or O(n^{7}
(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.
Close
An Algorithmic Framework for Segmenting Trajectories based on SpatioTemporal 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 spatiotemporal 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.
Close
AreaPreserving Subdivision Schematization
Wouter Meulemans (TU Eindhoven)
We describe an areapreserving subdivision schematization algorithm:
the area of each region in the input equals the area of the
corresponding region in the output. Our schematization is
axisaligned, the final output is a rectilinear subdivision. We first
describe how to convert a given subdivision into an areaequivalent
rectilinear subdivision. Then we define two areapreserving
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échetdistance) that show
that better schematizations might result in worse shapes.
Close