An optimal algorithm for computing visibility in the plane

Paul J. Heffernan; Joseph S.B. Mitchell

doi:10.1007/BFb0028282

An optimal algorithm for computing visibility in the plane

Paul J. Heffernan
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Cornell University

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

4 Scopus citations

Abstract

We give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm uses O(n) space and runs in optimal time Θ(n + h log h), improving the previous upper bound of O(n + log h).

Original language	English
Title of host publication	Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	437-448
Number of pages	12
ISBN (Print)	9783540475668
DOIs	https://doi.org/10.1007/BFb0028282
State	Published - 1991
Event	2nd Workshop on Algorithms and Data Structures, WADS 1991 - Ottawa, Canada Duration: Aug 14 1991 → Aug 16 1991

Publication series

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

Conference

Conference	2nd Workshop on Algorithms and Data Structures, WADS 1991
Country/Territory	Canada
City	Ottawa
Period	08/14/91 → 08/16/91

Access to Document

10.1007/BFb0028282

Cite this

Heffernan, P. J., & Mitchell, J. S. B. (1991). An optimal algorithm for computing visibility in the plane. In F. Dehne, J.-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings (pp. 437-448). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0028282

Heffernan, Paul J. ; Mitchell, Joseph S.B. / An optimal algorithm for computing visibility in the plane. Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro. Springer Verlag, 1991. pp. 437-448 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{df777d58376a4428a1711bc7c46ad0e0,

title = "An optimal algorithm for computing visibility in the plane",

abstract = "We give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm uses O(n) space and runs in optimal time Θ(n + h log h), improving the previous upper bound of O(n + log h).",

author = "Heffernan, \{Paul J.\} and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 2nd Workshop on Algorithms and Data Structures, WADS 1991 ; Conference date: 14-08-1991 Through 16-08-1991",

year = "1991",

doi = "10.1007/BFb0028282",

language = "English",

isbn = "9783540475668",

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

publisher = "Springer Verlag",

pages = "437--448",

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

booktitle = "Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings",

}

Heffernan, PJ & Mitchell, JSB 1991, An optimal algorithm for computing visibility in the plane. in F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 519 LNCS, Springer Verlag, pp. 437-448, 2nd Workshop on Algorithms and Data Structures, WADS 1991, Ottawa, Canada, 08/14/91. https://doi.org/10.1007/BFb0028282

An optimal algorithm for computing visibility in the plane. / Heffernan, Paul J.; Mitchell, Joseph S.B.
Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro. Springer Verlag, 1991. p. 437-448 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS).

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

TY - GEN

T1 - An optimal algorithm for computing visibility in the plane

AU - Heffernan, Paul J.

AU - Mitchell, Joseph S.B.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - We give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm uses O(n) space and runs in optimal time Θ(n + h log h), improving the previous upper bound of O(n + log h).

AB - We give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm uses O(n) space and runs in optimal time Θ(n + h log h), improving the previous upper bound of O(n + log h).

UR - https://www.scopus.com/pages/publications/85013554166

U2 - 10.1007/BFb0028282

DO - 10.1007/BFb0028282

M3 - Conference contribution

AN - SCOPUS:85013554166

SN - 9783540475668

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

SP - 437

EP - 448

BT - Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - 2nd Workshop on Algorithms and Data Structures, WADS 1991

Y2 - 14 August 1991 through 16 August 1991

ER -

Heffernan PJ, Mitchell JSB. An optimal algorithm for computing visibility in the plane. In Dehne F, Sack JR, Santoro N, editors, Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Springer Verlag. 1991. p. 437-448. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0028282

An optimal algorithm for computing visibility in the plane

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this