Date: Monday, June 18, 2007
Location: Utrecht University, Wentgebouw, room N017 (map below)
The fourth Dutch Computational Geometry Day will be held at Utrecht
University. The day will consist of presentations, featuring an
invited talk of Jack Snoeyink. After the day of talks there will be
a borrel and dinner for everyone interested in matters related to computational
geometry over some food (and, what isn't related to computational geometry?).
The dinner will be at a restaurant in Utrecht downtown, within easy reach
of the train station.
10.00 Arrival, coffee
10.20 Mostafa Vahedi: Caging Polygons with Two & Three Fingers
10.40 Rodrigo Silveira: Optimization for First Order Delaunay Triangulations
11.30 Invited talk: Jack Snoeyink: Putting Geometry in your Pipe
13.30 Mohammad Farshi: Region-Fault Tolerant Geometric Spanners
13.50 Sunayana Ghosh: Approximation by Conic Splines
14.10 Chris Gray: Triangulating Guarded Polygons
14.30 Peter van Oosterom: Poincare'-TEN data structure
15.20 Henk Meijer: Point-Set Embeddability with Edge Constraints
15.40 Herman Haverkort: Space-Filling Curves for Spatial Data Structures
16.00 Arjan Egges: The Motion Capture Lab
16.20 Shripad Thite: Frechet Distance Between Curves in the Plane with Obstacles
18.15 Dinner: Pamukkale (Turkish restaurant; reservation made under
the name Marc van Kreveld at 18.15), Mariaplaats 24.
Invited talk: Putting geometry in your pipe
Speaker: Jack Snoeyink
joint work with Martin Isenburg, Yuanxin Liu, and Johnathan Shewchuk
The "pipes" concept, originated by Doug McIlroy in 1972 for AT&T Unix v.3,
allowed users to combine simple tools opearating on data streams, with the
operating system time-slicing between the tool's processes. Some tools
(notably grep, awk, and sed) did stream processing on-the-fly, while others
(e.g. sort) were batch processes that read their whole input before producing
Since non-regular geometric data sets (such as point clouds, polygon soups,
and meshes) are difficult to characterize and represent, most tools operating
on these perform batch processing, at least to convert geometric data into
their own format for the operations that they support. For some geometry
processing and visualization tasks, however, the concept of finalization,
which simply documents in the data format when a data object will no longer
be needed, can support the best type of pipelined processing: results can
begin to be produced and used
well before the input data has been read.
We'll describe how finalization for points and meshes can be used in modules
for Delaunay triangulation, smoothing, compression, contour extraction,
rasterization, etc., leading to a pipelines that convert, for example,
terrain data from LIDAR (laser rangefinder) to contour maps, raster DEMs, or
TINs. Finalization reduces the memory footprint and enables sophisticated
algorithms on irregular data to compete with computation on grid-structured
data. Developers benefit from the elegance of pipes and filters by being able
to focus on the computation while the system takes care of time-slicing.
Users see an immediate benefit because they can abort after a few seconds if
the visualization is not quite what was desired.
On the campus map below, the Wentgebouw is in the South-West corner
of the Uithof. The building is a large cube.
Take bus 12 or 12s from Utrecht Central train station, and exit at the
very first bus stop on campus (Sorbonnelaan, blue circle close to the
maintained by: Marc van Kreveld