An optimal algorithm for finding the separation of simple polygons

Nancy M. Amato

doi:10.1007/3-540-57155-8_235

An optimal algorithm for finding the separation of simple polygons

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
Publisher	Springer-Verlag Berlin Heidelberg
Pages	48-59
Number of pages	12
ISBN (Print)	9783540571551
DOIs	https://doi.org/10.1007/3-540-57155-8_235
State	Published - 1993
Event	3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: Aug 11 1993 → Aug 13 1993

Publication series

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

Other

Other	3rd Workshop on Algorithms and Data Structures, WADS 1993
Country	Canada
City	Montreal
Period	8/11/93 → 8/13/93

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-57155-8_235

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

Amato, N. M. (1993). An optimal algorithm for finding the separation of simple polygons. In F. Dehne, J-R. Sack, N. Santoro, & S. Whitesides (Eds.), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings (pp. 48-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/3-540-57155-8_235

An optimal algorithm for finding the separation of simple polygons. / Amato, Nancy M.

Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer-Verlag Berlin Heidelberg, 1993. p. 48-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Amato, NM 1993, An optimal algorithm for finding the separation of simple polygons. in F Dehne, J-R Sack, N Santoro & S Whitesides (eds), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer-Verlag Berlin Heidelberg, pp. 48-59, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 8/11/93. https://doi.org/10.1007/3-540-57155-8_235

Amato NM. An optimal algorithm for finding the separation of simple polygons. In Dehne F, Sack J-R, Santoro N, Whitesides S, editors, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Springer-Verlag Berlin Heidelberg. 1993. p. 48-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-57155-8_235

Amato, Nancy M. / An optimal algorithm for finding the separation of simple polygons. Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro ; Sue Whitesides. Springer-Verlag Berlin Heidelberg, 1993. pp. 48-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dccd865ba2004fed9e08997c13c58cb8,

title = "An optimal algorithm for finding the separation of simple polygons",

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.",

author = "Amato, {Nancy M.}",

year = "1993",

doi = "10.1007/3-540-57155-8_235",

language = "English (US)",

isbn = "9783540571551",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "48--59",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",

booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

note = "3rd Workshop on Algorithms and Data Structures, WADS 1993 ; Conference date: 11-08-1993 Through 13-08-1993",

}

TY - GEN

T1 - An optimal algorithm for finding the separation of simple polygons

AU - Amato, Nancy M.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21144469096&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144469096&partnerID=8YFLogxK

U2 - 10.1007/3-540-57155-8_235

DO - 10.1007/3-540-57155-8_235

M3 - Conference contribution

AN - SCOPUS:21144469096

SN - 9783540571551

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

SP - 48

EP - 59

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer-Verlag Berlin Heidelberg

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

Y2 - 11 August 1993 through 13 August 1993

ER -