Dynamically maintaining the visibility graph

Gert Vegter

doi:10.1007/BFb0028281

Dynamically maintaining the visibility graph

Gert Vegter^*

^*Corresponding author for this work

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

5 Citations (Scopus)

Abstract

An algorithm is presented to maintain the visibility graph of a set of N line segments in the plane in O(log2 N + K log N) time, where K is the total number of arcs of the visibility graph that are destroyed or created upon insertion or deletion of a line segment. The line segments should be disjoint, except possibly at their end-points. The algorithm maintains the visibility diagram, a 2-dimensional cell complex whose 0-dimensional cells correspond to arcs of the visibility graph.

The method can also be applied to determine the visibility polygon of a query point, and also to plan the motion of a rod amidst a dynamically changing set of obstacles. The time complexity of both applications meets the optimal time bounds for their static counterparts.

Original language	English
Title of host publication	Algorithms and Data Structures
Editors	F DEHNE, SACK, N SANTORO
Place of Publication	Berlin
Publisher	Springer
Pages	425-436
Number of pages	12
ISBN (Print)	3-540-54343-0
DOIs	https://doi.org/10.1007/BFb0028281
Publication status	Published - 1991
Event	2ND WORKSHOP ON ALGORITHMS AND DATA STRUCTURES ( WADS 91 ) - , Canada Duration: 14-Aug-1991 → 16-Aug-1991

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	519
ISSN (Print)	0302-9743

Other

Other	2ND WORKSHOP ON ALGORITHMS AND DATA STRUCTURES ( WADS 91 )
Country/Territory	Canada
Period	14/08/1991 → 16/08/1991

Access to Document

10.1007/BFb0028281

Handle.net

Persistent link

Cite this

@inproceedings{4d66a312af5341e2bbf76c5624f44234,

title = "Dynamically maintaining the visibility graph",

abstract = "An algorithm is presented to maintain the visibility graph of a set of N line segments in the plane in O(log2 N + K log N) time, where K is the total number of arcs of the visibility graph that are destroyed or created upon insertion or deletion of a line segment. The line segments should be disjoint, except possibly at their end-points. The algorithm maintains the visibility diagram, a 2-dimensional cell complex whose 0-dimensional cells correspond to arcs of the visibility graph.The method can also be applied to determine the visibility polygon of a query point, and also to plan the motion of a rod amidst a dynamically changing set of obstacles. The time complexity of both applications meets the optimal time bounds for their static counterparts.",

author = "Gert Vegter",

year = "1991",

doi = "10.1007/BFb0028281",

language = "English",

isbn = "3-540-54343-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "425--436",

editor = "F DEHNE and SACK and N SANTORO",

booktitle = "Algorithms and Data Structures",

note = "2ND WORKSHOP ON ALGORITHMS AND DATA STRUCTURES ( WADS 91 ) ; Conference date: 14-08-1991 Through 16-08-1991",

}

TY - GEN

T1 - Dynamically maintaining the visibility graph

AU - Vegter, Gert

PY - 1991

Y1 - 1991

N2 - An algorithm is presented to maintain the visibility graph of a set of N line segments in the plane in O(log2 N + K log N) time, where K is the total number of arcs of the visibility graph that are destroyed or created upon insertion or deletion of a line segment. The line segments should be disjoint, except possibly at their end-points. The algorithm maintains the visibility diagram, a 2-dimensional cell complex whose 0-dimensional cells correspond to arcs of the visibility graph.The method can also be applied to determine the visibility polygon of a query point, and also to plan the motion of a rod amidst a dynamically changing set of obstacles. The time complexity of both applications meets the optimal time bounds for their static counterparts.

AB - An algorithm is presented to maintain the visibility graph of a set of N line segments in the plane in O(log2 N + K log N) time, where K is the total number of arcs of the visibility graph that are destroyed or created upon insertion or deletion of a line segment. The line segments should be disjoint, except possibly at their end-points. The algorithm maintains the visibility diagram, a 2-dimensional cell complex whose 0-dimensional cells correspond to arcs of the visibility graph.The method can also be applied to determine the visibility polygon of a query point, and also to plan the motion of a rod amidst a dynamically changing set of obstacles. The time complexity of both applications meets the optimal time bounds for their static counterparts.

U2 - 10.1007/BFb0028281

DO - 10.1007/BFb0028281

M3 - Conference contribution

SN - 3-540-54343-0

T3 - Lecture Notes in Computer Science

SP - 425

EP - 436

BT - Algorithms and Data Structures

A2 - DEHNE, F

A2 - SACK, null

A2 - SANTORO, N

PB - Springer

CY - Berlin

T2 - 2ND WORKSHOP ON ALGORITHMS AND DATA STRUCTURES ( WADS 91 )

Y2 - 14 August 1991 through 16 August 1991

ER -

Dynamically maintaining the visibility graph

Abstract

Publication series

Other

Access to Document

Handle.net

Fingerprint

Cite this