FAST NEAREST NEIGHBOR ALGORITHMS ON A LINEAR ARRAY WITH A RECONFIGURABLE PIPELINED BUS SYSTEM

Abstract

Abstract We present efficient algorithms for the nearest neighbor problem defined in an n × n binary image. We show that using a linear array with a reconfigurable pipelined bus system (LARPBS) of n2 processors, the nearest neighbor problem can be solved in O(loglogn) time, and using an LARPBS of n2+∊ processors, for any fixed constant ∊>0. the nearest neighbor problem can be solved in O(l) time. We also show that the nearest neighbor problem can be solved on an LARPBS of n2 processors in O(1) time with high probability. Keywords: Image analysisNearest-neighbor problemParallel algorithmReconfigurable optical busTime complexity Additional informationNotes on contributorsYI PAN Corresponding author. This author's research was supported in part by the National Science Foundation under Grants CCR-9211621 and CCR-9503882, the Air Force Avionics Laboratory, Wright Laboratory, under Grant F33615-C-22I8, an Ohio Board of Regents Investment Fund Competition Grant, and an Ohio Board of Regents Research Challenge Grant. E-mail: [e-mail] KEQIN LI This author's research was supported in part by the NASA/University Joint Venture (JOVE) in Research Program of National Aeronautics and Space Administration and the Research Foundation of State University of New York at New Paltz. The author was also supported by the NASA/ASEE Summer Faculty Fellowship Program. E-mail:[e-mail] SI-QING ZHENG This author's research was supported in part by the National Science Foundation under Grant ECS-9626215 and Louisiana Grant LEQSF (1996-99)-RD-A-16. E-mail: [e-mail].