Scanbox Approach to Shape Reconstruction for Automated Reticle Inspection

Abstract

The paper describes a generalization of the scanline approach [1] to reconstruction of the shape of planar object represented by a discrete point set with a given distance threshold d. This problem arises in applications of VLSI layout image processing, e.g., during automated reticle inspection.

Two algorithms are presented, with time complexities O(min {n^{2, (n + t)log n}) and O(n log n), respectively, where n is the number of input points, t is the number of fixed-radius neighbor pairs. The first one is applicable for sparse point sets, e.g., for almost-grid point sets. In addition, ideas from the first algorithm, combined with the scanbox approach lead to the second algorithm efficient in the general case.}