Given two planar sets A and B, we examine the problem of determining the smallest ϵ such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within distance ϵ of some member of B. We establish upper bounds on the combinatorial complexity of this subproblem in model-based computer vision, when the sets A and B contain points, line segments, or (filled-in) polygons. We also show how to use our methods to substantially improve on existing algorithms for finding the minimum Hausdorff distance under Euclidean motion.

Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that no such element exists. Time and work optimal algorithms for this problem are known on all the PRAM models but the running time of the best previous hypercube algorithm is optimal only when the number of processors p satisfies 1/spl les/p/spl les/n/((lg/sup 3/ n)(lg lg n)/sup 2/). In this paper, we prove that any normal hypercube algorithm requires /spl Omega/(M) processors to solve the ANSV problem in O(lg n) time, and we present the first normal hypercube ANSV algorithm that is optimal for all values of n and p. We use our ANSV algorithm to give the first O(lg n)-time n-processor normal hypercube algorithms for triangulating a monotone polygon and for constructing a Cartesian tree.

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n>

Article Parallel searching in generalized Monge arrays with applications Share on Authors: A. Aggarwal IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , D. Kravets Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , J. Park Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , S. Sen Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 259–268https://doi.org/10.1145/97444.97693Online:01 May 1990Publication History 11citation348DownloadsMetricsTotal Citations11Total Downloads348Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access