An optimal algorithm for finding the separation of simple polygons

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
PublisherSpringer-Verlag Berlin Heidelberg
Pages48-59
Number of pages12
ISBN (Print)9783540571551
DOIs
StatePublished - 1993
Event3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada
Duration: Aug 11 1993Aug 13 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume709 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Workshop on Algorithms and Data Structures, WADS 1993
CountryCanada
CityMontreal
Period8/11/938/13/93

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An optimal algorithm for finding the separation of simple polygons'. Together they form a unique fingerprint.

Cite this