FINDING A CLOSEST VISIBLE VERTEX PAIR BETWEEN 2 POLYGONS
|
Academic Article
individual record
abstract
Given nonintersecting simple polygons P and Q, two vertices pP 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), pP and qQ. 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
publication outlet
ALGORITHMICA
author list (cited authors)
AMATO, N. M.
publication date
1995
publisher
Springer Nature
Publisher
keywords
- Simple Polygon
- Visible Vertex Distance
- Pram
- Sequential Algorithm
- Parallel Algorithm
citation count
3