The Dutch Computational Geometry Day of 2009 will take place on October 21, at Utrecht University.
The talks will be at the Kruytgebouw, room O123 (east wing, first floor).

Update: More than 40 people attended the DCGD, probably setting a new record!

Final program

10:00

Welcome coffee

10:30

Bettina Speckmann (TU/e)

Geometric Simultaneous Embeddings of a Graph and a Matching
[Abstract]

10:55

Rodrigo Silveira (UU)

Detecting Hotspots in Geographic Networks
[Abstract]

11:20

Coffee break, with a selection of Dutch delicacies

11:45

Invited talk:

Ferjan Ormeling (UU)

Biography of a school atlas: where the Dutch learn
their geography

12:30

Dutch-style lunch at the Kruytgebouw

13:30

Roland Geraerts (UU)

Planning Short Paths with Clearance using Explicit Corridors
[Abstract]

13:55

Marcel Roeloffzen (TU/e)

Finding structures on imprecise points

14:20

Coffee break, with a selection of some other Dutch delicacies

14:45

Jack Snoeyink (UNC)

Efficient computation of the discrete Voronoi diagram without the InCircle predicate
[Abstract]

15:10

Kevin Buchin (TU/e)

Computing Delaunay Triangulations from Simpler Structures
[Abstract]

15:35

Hugo Ledoux (TU Delft)

Validating and repairing planar partitions using the constrained Delaunay triangulation

16:00

Coffee break, with a selection of some more Dutch delicacies

16:25

Stefan Langerman (ULB)

Every Large Point Set contains Many Collinear Points or an Empty Pentagon

16:50

Maarten Löffler (UU)

Connect the Dot: Computing Feed-links with Minimum Dilation
[Abstract]

3rd Dutch Computational Geometry Day, Eindhoven, July 3, 2006.

2nd Dutch Computational Geometry Day, Utrecht, January 18, 2005.

1st Dutch Computational Geometry Day, 2003 or 2004?

How to get there

The talks will take place at the Kruytgebouw, room O123 (East wing, first floor).
The building is located at the university campus De Uithof, about 5 km to the east of the center of Utrecht.

The Kruytgebouw looks more or less like this:

It's a cross-shaped building, very easy to recognize for those arriving by helicopter: View Larger Map
Warning: the Google Maps photo is a bit old: one of the bus stops is shown in the middle of the grass. The location of the bus stop is correct, it's just that, recently, the road was moved to the other side of the parking lot.

By public transport: from the Utrecht Central Station: take bus 11 or 12/12s, get off at stop Botanische Tuinen (line 11) or Padualaan (line 12/12s).

By car: use your favourite route planner and ask it to get you to Padualaan 8, Utrecht.

By helicopter: keep your eyes open for a cross-shaped building, how many can there be?

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.

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.

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.

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.

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.

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.