Optimal geometric algorithms for digitized pictures on an optical mesh

Optimal parallel algorithms are presented for finding geometric properties of digitized images on an optical mesh. These include O(log N) time solutions for identifying and labeling figures, computing convexity properties, determining distances, etc. The proposed optical mesh consists of a two-dimensional array of processors which are interconnected through an optical medium. Using free space optical beams, the interconnection topology can be reconfigured dynamically. The computational lower bound of a generic model reflecting such an organization is shown. Unlike the VLSI models, there are no planarity constraints, since the optical beams can cross each other without any interference. The relationships between the shared memory models and the proposed optical model of computation and its possible physical implementations are studied