Abstract
An efficient algorithm for simultaneously generating and classifying space tiles in a building block based layout is presented. Our contribution is to combine two wellknown techniques, plane-sweep and shadowing, to form a fast algorithm. Two data structures are used to represent the shadows and the block edges. Types of shadows and edges are categorized. Whether a bottleneck or dominant tile will be generated when a shadow on the sweeping line hits a block edge is tabulated. The computation time complexity of our algorithm is O(n log n), where n is the number of building blocks. Experimental results show that this algorithm is superior to other approaches. Extensions to and applications of this algorithm are discussed. © 1990.