Step into Computational Geometry Notebook III
F. P. Preparata · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1981
In this notebook we present a collection of three new results in planar computational geometry. The first problem is to test a given n-vertex simple polygon for monotonicity; this problem can be optimally solved in time theta(n). The second result is an improved algorithm for the rectangle enclosure problem; this algorithm improves over an existing one by using optimal space theta(n). Finally, the third result is the construction, in time 0(nlogn), of the shortest path between two points in the interior of an n-vertex polygon P, when the path is constrained to lie within P. (Author)