An isothetic view of computational geometry. (English) Zbl 0614.68078

Wood, Derick

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

MSC:

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

Keywords:

Isothetic polygons; VLSI-design; survey; Intersection; Convexity; Combinational; Clustering; Visibility

Citations:

Zbl 0575.00022