4th Dutch Computational Geometry Day

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.

Tentative program:

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.00-11.30 Break

11.30 Invited talk: Jack Snoeyink: Putting Geometry in your Pipe

12.15-13.30 Lunch

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

14.50-15.20 Break

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

16.45 Drinks

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 output.
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.

Location: 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 label A27).

campus map

maintained by: Marc van Kreveld