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

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 |