2012/07/17 by Helmut Alt, Alt, Helmut, Ludmila Scharf +1
Computer Science · #Computational Geometry (cs.CG) #Computer Vision and Pattern Recognition (cs.CV) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.CG #cs.CV #cs.DC
paper · pdf · doi:10.48550/arxiv.1207.3962
arxiv created 2012/07/17 · arxiv updated 2012/07/18
We show that the Hausdorff distance for two sets of non-intersecting line segments can be computed in parallel in O(log2 n) time using O(n) processors in a CREW-PRAM computation model. We discuss how some parts of the sequential algorithm can be performed in parallel using previously known parallel algorithms; and identify the so-far unsolved part of the problem for the parallel computation, which is the following: Given two sets of x-monotone curve segments, red and blue, for each red segment find its extremal intersection points with the blue set, i.e. points with the minimal and maximal x-coordinate. Each segment set is assumed to be intersection free. For this intersection problem we describe a parallel algorithm which completes the Hausdorff distance computation within the stated time and processor bounds.