An optimal algorithm computing edge-to-edge visibility in a simple polygon

Mikkel Abrahamsen

An optimal algorithm computing edge-to-edge visibility in a simple polygon

Department of Computer Science

5 Citations (Scopus)

Abstract

Let P be a given, simple polygon with n vertices. We present a new O(n)-time algorithm to compute the visible part of one edge from another edge of P. The algorithm does not alter the input and only uses O(1) variables and is therefore a constant-workspace algorithm. The algorithm can be used to make a constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices of the resulting polygon, and a constant-workspace algorithm for computing a minimum link path between two points inside a simple polygon in O(n²) time.

Original language	English
Title of host publication	Proceedings of the 25th Canadian Conference on Computational Geometry : CCCG 2013
Number of pages	6
Publication date	2013
Pages	157-162
Publication status	Published - 2013
Event	Canadian Conference on Computational Geometry 2013 - Waterloo, Ontario, Canada Duration: 8 Aug 2013 → 10 Aug 2013 Conference number: 25

Conference

Conference	Canadian Conference on Computational Geometry 2013
Number	25
Country/Territory	Canada
City	Waterloo, Ontario
Period	08/08/2013 → 10/08/2013

Access to Document

An Optimal Algorithm Computing Edge-to-Edge Visibility in a Simple PolygonFinal published version, 307 KB

http://cccg.ca/proceedings/2013/papers/paper_34.pdf

Cite this

@inproceedings{8804d8132f694e1c850f09b3de9bfc5f,

title = "An optimal algorithm computing edge-to-edge visibility in a simple polygon",

abstract = "Let P be a given, simple polygon with n vertices. We present a new O(n)-time algorithm to compute the visible part of one edge from another edge of P. The algorithm does not alter the input and only uses O(1) variables and is therefore a constant-workspace algorithm. The algorithm can be used to make a constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices of the resulting polygon, and a constant-workspace algorithm for computing a minimum link path between two points inside a simple polygon in O(n2) time.",

author = "Mikkel Abrahamsen",

year = "2013",

language = "English",

pages = "157--162",

booktitle = "Proceedings of the 25th Canadian Conference on Computational Geometry",

note = "Canadian Conference on Computational Geometry 2013 ; Conference date: 08-08-2013 Through 10-08-2013",

}

TY - GEN

T1 - An optimal algorithm computing edge-to-edge visibility in a simple polygon

AU - Abrahamsen, Mikkel

N1 - Conference code: 25

PY - 2013

Y1 - 2013

N2 - Let P be a given, simple polygon with n vertices. We present a new O(n)-time algorithm to compute the visible part of one edge from another edge of P. The algorithm does not alter the input and only uses O(1) variables and is therefore a constant-workspace algorithm. The algorithm can be used to make a constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices of the resulting polygon, and a constant-workspace algorithm for computing a minimum link path between two points inside a simple polygon in O(n2) time.

AB - Let P be a given, simple polygon with n vertices. We present a new O(n)-time algorithm to compute the visible part of one edge from another edge of P. The algorithm does not alter the input and only uses O(1) variables and is therefore a constant-workspace algorithm. The algorithm can be used to make a constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices of the resulting polygon, and a constant-workspace algorithm for computing a minimum link path between two points inside a simple polygon in O(n2) time.

M3 - Article in proceedings

SP - 157

EP - 162

BT - Proceedings of the 25th Canadian Conference on Computational Geometry

T2 - Canadian Conference on Computational Geometry 2013

Y2 - 8 August 2013 through 10 August 2013

ER -

An optimal algorithm computing edge-to-edge visibility in a simple polygon

Abstract

Conference

Access to Document

Fingerprint

Cite this