An Optimal Algorithm for Determining the Separation of Two Nonintersecting Simple Polygons
Nancy M. Amato · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1992
TERMS (Continua on reverse if nacassary and identify by block number)separation, simple polygons, sequential, parallel 19.ABSTRACT (Continue on reverse if nacassary and identify by block number) Given nonintersecting simple polygons P and Q, their separation, denoted by <r(P, Q), is defined to be the minimum distance between their boundaries; a pair of points p € P and q € Q realize cr{P,Q), if d(p,q) = <r(P,<3).We present an optimal Q(N) time algorithm for determining the separation of two disjoint simple polygons P and Q, and finding a pair of points (p, q), p € P and q € Q, realizing