An optimal parallel algorithm for the all-nearest-foreign-neighborsproblem in arbitrary dimensions

摘要

Given a set S of n points in RD, D⩾2. Eachpoint p∈S is assigned a color c(p) chosen from a fixed color set.The All-Nearest-Foreign-Neighbors Problem (ANFNP) is to find for eachpoint p∈S its nearest foreign neighbors, i.e. the set of all pointsin S/{p} that are closest to p among the points in S with a colordifferent from c(p). We introduce the Well Separated Color Decomposition(WSCD) which gives an optimal O(log n) parallel algorithm to solve theAMFNP, for fixed dimension D⩾2 and fixed Lt-metricd_t, 1⩽t⩽∞. The WSCD is based upon the WellSeparated Pair Decomposition (Callahan et al., 1992). The ANFNP findsextensive applications in VLSI design and verification for twodimensions, and in traffic-control systems and Geographic InformationSystems for D>2 dimensions. To the best of our knowledge, this is theonly known optimal parallel algorithm for the ANFNP