A fast algorithm for the Boolean masking problem. (English) Zbl 0622.68045

Ottmann, Thomas; Widmayer, Peter; Wood, Derick

Comput. Vision Graphics Image Process. 30, 249-268 (1985).

An algorithm is presented for the calculation of Boolean combinations between layers of a VLSI circuit layout. Each layer is assumed to contain only polygons, which are specified by their edges; the output is also polygonal. The algorithm runs in \(O((n+k)(r+\log n))\) time and O(nr) space, where n is the total number of edges on all layers, k is the number of edge intersection, and r is the number of layers. Also a number of restrictions on the general problem are discussed which lead to substantial improvements in the time bounds. It is proved that when the polygons are presented using a hierarchical description language the problem becomes NP-hard. Finally how this approach can be used to solve the i-contour problem of computational geometry and the hidden-line- elimination problem of computer graphics is discussed.

MSC:

68Q25	Analysis of algorithms and problem complexity
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68U99	Computing methodologies and applications
94C15	Applications of graph theory to circuits and networks

Keywords:

Boolean mask combinations; algorithm; calculation of Boolean combinations between layers of a VLSI circuit layout; i-contour problem; computational geometry; hidden-line-elimination problem; computer graphics