About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
We study the class of rectilinear polygons, called X - 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 of X - Y polygons and present efficient algorithms for computing the X - Y convex hulls of an X - Y polygon and of a set of X - Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, the X - Y convex hull of a set of X - Y polygons may not exist. The condition under which the X - Y convex hull exists is given and an algorithm for testing if the given set of X - Y polygons satisfies the condition is also presented. © 1983 BIT Foundations.