Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm

DOI10.1016/0166-218X(90)90084-PzbMath0707.68040OpenAlexW2045347717MaRDI QIDQ919827

Baruch Schieber, Uzi Vishkin

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90084-p

zbMATH Keywords

parallel computationlower boundparallel complexitymatching algorithmnearest neighborCRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Fast integer merging on the EREW PRAM ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon ⋮ Space-efficient parallel merging

Cites Work

• Unnamed Item
• Comments on the all nearest-neighbor problem for convex polygons
• Routing, merging, and sorting on parallel models of computation
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Parallel computational geometry
• The all nearest-neighbor problem for convex polygons
• A note on the all nearest-neighbor problem for convex polygons
• Efficient piecewise-linear function approximation using the uniform metric
• Searching, Merging, and Sorting in Parallel Computation
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Finding the maximum, merging, and sorting in a parallel computation model
• An O(n2log n) parallel max-flow algorithm
• Sorting and Merging in Rounds
• Parallelism in Comparison Problems