FINDING A CLOSEST VISIBLE VERTEX PAIR BETWEEN 2 POLYGONS Academic Article

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

• Amato, Nancy

published proceedings

• ALGORITHMICA

author list (cited authors)

• AMATO, N. M.

citation count

• 3

complete list of authors

• AMATO, NM

publication date

• August 1995

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• Parallel Algorithm
• Pram
• Sequential Algorithm
• Simple Polygon
• Visible Vertex Distance

Digital Object Identifier (DOI)

• 10.1007/BF01293668

start page

• 183

end page

• 201

volume

• 14

issue

• 2

URL

• http://dx.doi.org/10.1007/bf01293668