Fernando Martinez, Juntao Chen, et al.
AAAI 2025
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.
Fernando Martinez, Juntao Chen, et al.
AAAI 2025
Imran Nasim, Melanie Weber
SCML 2024
George Markowsky
J. Math. Anal. Appl.
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.