zbMATH — the first resource for mathematics

An isothetic view of computational geometry. (English) Zbl 0614.68078
Computational geometry, Mach. Intell. Pattern Recognition 2, 429-459 (1985).
[For the entire collection see Zbl 0575.00022.]
Isothetic polygons are polygons with sides parallel to two axes. The field of application is mainly VLSI-design-like.
This paper is a survey of what is known about isothetic polygons (which is a lot more than VLSI people may want to know). The problems are categorized neatly, in Intersection, Convexity, Combinational, Clustering and Visibility. For each of the areas, the important questions are formulated and answered, if an answer is known, by the best possible solution. The time and space complexities are given. The paper contains 71 references, and, where instructive, proofs.
The paper is well-written and highly readable. A useful paper for an area that raises, which answers, both academic and practical questions.
Reviewer: L.Dorst

68U99 Computing methodologies and applications
51M20 Polyhedra and polytopes; regular figures, division of spaces