FINDING A CLOSEST VISIBLE VERTEX PAIR BETWEEN 2 POLYGONS | Academic Article individual record
abstract

Given nonintersecting simple polygons P and Q, two vertices pεP and qε Q are said to be visible if {Mathematical expression} does not properly intersect P or Q. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q), pεP and qεQ. The algorithm runs in time O(log n) using O(n) processors on a CREW PRAM, where n=|P|+|Q|. This algorithm can be implemented serially in Θ(n) time, which gives a new optimal sequential solution for this problem. © 1995 Springer-Verlag New York Inc.

authors
author list (cited authors)
AMATO, N. M.
publication date
1995
published in
Algorithmica Journal
keywords
  • Simple Polygon
  • Sequential Algorithm
  • Visible Vertex Distance
  • Pram
  • Parallel Algorithm
citation count

3