Computational Geometry-Methods, Algorithms and Applications: International Workshop on Computational Geometry CG’91 Bern, Switzerland, March 21–22, 1991 Proceedings

Franz Aurenhammer, Gerd Stöckl, Emo Welzl (auth.), H. Bieri, H. Noltemeier (eds.)9780387548913, 0-387-54891-2

This volume presents the proceedings of the Seventh International Workshop on Computational Geometry, CG’91, held at the University of Berne, Switzerland, March 21/22, 1991. Computational geometry is not a precisely defined field. Often, it is understood as a nearly mathematical discipline, dealing mainly with complexity questions concerning geometrical problems and algorithms. But often too, and perhaps increasingly, questions of more practical relevance are central, such as applicability, numerical behavior and performance for all kinds of input size. Topics considered in CG’91 include: – Generalizations and applications of the Voronoi diagram – Problems with rectangular objects – Path determination – Moving objects – Visibility questions – Layout problems – Representation of spatial objects and spatial queries – Problems in higher dimensions – Implementation questions – Relations to artificial intelligence.

---

Table of contents :
The post office problem for fuzzy point sets….Pages 1-11
An optimal algorithm for approximating a set of rectangles by two minimum area rectangles….Pages 13-25
An on-line algorithm for constructing sweep planes in regular position….Pages 27-35
Performance analysis of three curve representation schemes….Pages 37-56
Preclassification and delayed classification of boundary entities in arbitrary dimensions….Pages 57-69
On the morphology of polytopes in ℝ d ….Pages 71-83
Robustness in geometric modeling — Tolerance-based methods….Pages 85-101
On shortest networks for classes of points in the plane….Pages 103-111
Determination of the symmetries of polyhedra and an application to object recognition….Pages 113-121
Moving along a street (extended abstract)….Pages 123-140
Planar geometric reasoning with the theory of hints….Pages 141-159
Solving algebraic systems in Bernstein-Bézier representation….Pages 161-169
XYZ: A project in experimental geometric computation….Pages 171-186
Implementing the XYZ GeoBench: A programming environment for geometric algorithms….Pages 187-202
Computing the rectilinear link diameter of a polygon….Pages 203-215
Layout of flexible manufacturing systems — selected problems….Pages 217-225
Dynamic Voronoi diagrams in motion planning….Pages 227-236
Generating triangulations of 2-manifolds….Pages 237-248
The TR * -tree: A new representation of polygonal objects supporting spatial queries and operations….Pages 249-263
A Voronoi diagram based adaptive k-means-type clustering algorithm for multidimensional weighted data….Pages 265-275
A Generalization of staircase visibility….Pages 277-287
A new simple linear algorithm to recognize interval graphs….Pages 289-308
Predictions about collision free paths from intersection tests….Pages 309-320