Steps into Computational Geometry: Notebook II.
Abstract
In this notebook a collection of new results is presented in computational geometry, which all concern problems of planar geometry. The first problem is that of triangulating a simple n-vertex polygon; we show that this can be done in time 0(nlogn), by first decomposing in time 0(nlogn) the given polygon into a collection of special polygons, called monotone, which can be individually triangulated in time proportional to their numbers of edges. The second result concerns that all-nearest neighbor problem for an n-vertex polygon: a surprising result is that, also no method faster than 0(nlogn) is known for constructing the Voronoi diagram of a convex polygon, the all-nearest-neighbor problem can be solved in time 0(n). Finally, we show the feasibility of an optimal real-time algorithm for constructing the convex hull of a set of n points in the plane. This algorithm constructs the hull by successive updates, using total 0(nlogn) time - which is optimal - with an interpoint delay 0(logn), which gives the real-time property. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1977
- Accession Number
- ADA056271
Entities
People
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign