An optimal algorithm for finding the separation of simple polygons Conference Paper

abstract

• Springer-Verlag Berlin Heidelberg 1993. Given simple polygons P and Q, their separation, denoted by (P,Q), is defined to be the minimum distance between their boundaries. We present an optimal (N) algorithm for determining the separation of two simple polygons P and Q, where |P|+|Q|=|N|. The best previous algorithm for this problem is due to Kirkpatrick and has complexity O(N log N). In addition, a parallel version of our algorithm can be implemented in O(log N) time using O(N) processors on a CREW PRAM. Our results are obtained by providing a unified treatment of the separation and the closest visible vertex problems for simple polygons.

authors

• Amato, Nancy

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Amato, N. M.

complete list of authors

• Amato, NM

publication date

• January 1993

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 13

• 9783540571551

start page

• 48

end page

• 59

volume

• 709 LNCS