Gerrit Gruben

The Kinetic Framework of Computational Geometry and its Applications

Betreuer: Prof. Dr. Günter Rote
Abschluss: Diplom
Abgabedatum: 25.03.2014


In 1983 Leo Guibas, Lyle Ramshaw, and Jorge Stolfi published "The Kinetic Framework for Computational Geometry" ([GRS83]). In this framework oriented polygonal outlines, the polygonal tracings, are defined.

Polygonal tracings generalise polygons in a way that enables the definition of topological quantities, such as the winding number, the degree, and a new quantity: the sweep number. A calculus of tracings is introduced, involving the convolution and product - a generalisation of intersection - of tracings. Interesting theorems relating these quantities and operations are discovered.

Applications of this theory include the computation of Minkowski sums of polygons with the convolution method. This method beats decomposition methods in terms of run-time efficiency by a factor of two to five ([Wei06]).

Convexity is described in a novel way by convex tracings. Convex tracings and their generalisation, the monostrofic tracings, are used to solve classical problems involving convex polygons. This encompasses, but is not limited to, finding common tangents and solving the containment problem for three polygons. A notion of duality is introduced by an oriented variant of projective geometry.

This thesis fills the nowadays still existing gap of proofs left by [GRS83].


[GRS83] L. Guibas, L. Ramshaw, and J. Stolfi, “A kinetic framework for computational geometry,” Foundations of Computer Science, IEEE Annual Symposium on, vol. 0, pp. 100–111, 1983.

[Wei06] R. Wein, “Exact and efficient construction of planar minkowski sums using the convolution method,” in ESA, 2006, pp. 829–840.