Ralf Hartmut Güting
Index Terms
- An optimal contour algorithm for iso-oriented rectangles
Recommendations
An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
Given n rectangles R"1,...,R"n on the plane with sides parallel to the coordinate axes, Lipski and Preparata (1981) [1] have presented a @Q(nlogn) time and O(nlogn) space algorithm for computing the non-trivial circuits of the union U=R"1@?...@?R"n. In ...
Largest inscribed rectangles in convex polygons
We consider approximation algorithms for the problem of computing an inscribed rectangle having largest area in a convex polygon on n vertices. If the order of the vertices of the polygon is given, we present a randomized algorithm that computes an ...
Reviews
A. R. Forrest
The paper describes a time-optimum algorithm for examining the contour of the union of n iso-oriented rectangles in 2-space (iso-oriented rectangles have sides parallel to the coordinate axes). The algorithm is a development of the line sweep algorithm reported by Lipski and Preparata [1] using a modified data structure, the contracted segment tree. This permits insertion and deletion of an interval in O(log n) time, but can also report free portions of a line covered by a new interval in a time proportional to the number of free parts. It is not clear whether the new data structure would have advantages of efficiency in a practical implementation compared with rather simpler data structures. The algorithm bears a striking resemblance to the scan-line oriented hidden surface algorithms developed by Watkins [2]. It might be advantageous to reexamine Watkins' algorithm with a view to utilizing more modern data structures.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments