In the last thirty years Computational Geometry has emerged as a new discipline from the field of design and analysis of algorithms. That dis cipline studies geometric problems from a computational point of view, and it has attracted enormous research interest. But that interest is mostly concerned with Euclidean Geometry (mainly the plane or Eu clidean 3-dimensional space). Of course, there are some important rea sons for this occurrence since the first applieations and the bases of all developments are in the plane or in 3-dimensional space. But, we can find also some exceptions, and so Voronoi diagrams on the sphere, cylin der, the cone, and the torus have been considered previously, and there are manY works on triangulations on the sphere and other surfaces. The exceptions mentioned in the last paragraph have appeared to try to answer some quest ions which arise in the growing list of areas in which the results of Computational Geometry are applicable, since, in practiee, many situations in those areas lead to problems of Com putational Geometry on surfaces (probably the sphere and the cylinder are the most common examples). We can mention here some specific areas in which these situations happen as engineering, computer aided design, manufacturing, geographie information systems, operations re search, roboties, computer graphics, solid modeling, etc.

Preface. Acknowledgments. 1: Preliminaries. 1. Introduction. 2. Notations and Terminology. 3. Orbifolds. 4. Point Location and Range Searching. 5. Notes and comments. 2: Euclidean Position. 1. Introduction. 2. Euclidean Position. 3. Cylindrical position in the Torus. 4. Euclidean position in Orbifolds and in General Surfaces. 5. Notes and comments. 3: Convex Hull. 1. Introduction. 2. Hyperconvex Hull. 3. Metrically Convex Hull. 4. Analysis of complexity. 5. Minimum enclosing polygon. 6. Notes and comments. 4: Voronoi Diagrams. 1. Introduction. 2. Voronoi diagrams. 3. Proximity problems and Voronoi diagrams. 4. Furthest point Voronoi diagram. 5. Generalized Voronoi diagrams. 6. Notes and Comments. 5: RADII. 1. Introduction. 2. The Width of a Convex Set on the Sphere. 3. Circumradius. 4. Diameter. 5. Maximum and minimum distances. 6. Notes and remarks. 6: Visibility. 1. Introduction. 2. Stabbing line segments. 3. Visibility in the presence of obstacles. 4. Notes and comments. 7: Triangulations. 1. Introduction. 2. Triangulations on the cylinder. 3. Triangulations on the sphere and on the torus. 4. The graph of triangulations on non-planar surfaces. 5. Notes and Comments. References. Topic Index. Author Index.

Hersteller:
Springer Verlag GmbH
juergen.hartmann@springer.com
Tiergartenstr. 17
DE 69121 Heidelberg