DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA056271
Title:
Steps into Computational Geometry: Notebook II.
Corporate Author:
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Report Date:
1977-09-01
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 0nlogn, by first decomposing in time 0nlogn 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 0nlogn is known for constructing the Voronoi diagram of a convex polygon, the all-nearest-neighbor problem can be solved in time 0n. 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 0nlogn time - which is optimal - with an interpoint delay 0logn, which gives the real-time property. Author
Descriptive Note:
Technical rept.,
Pages:
0029
Contract Number:
DAAB07-72-C-0259
Contract Number 2:
NSF-MCS76-17321
File Size:
10.46MB
