ISSN:
1572-9125
Keywords:
Analysis of algorithms
;
convexity
;
rectilinear polygons
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01933620
Permalink
