Computing a shortest weakly externally visible line segment for a simple polygon

Binay K. Bhattacharya; Asish Mukhopadhyay; Godfried T. Toussaint

doi:10.1142/S0218195999000078

Computing a shortest weakly externally visible line segment for a simple polygon

Binay K. Bhattacharya, Asish Mukhopadhyay, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A simple polygon P is said to be weakly externally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of pq lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.

Original language	English (US)
Pages (from-to)	81-96
Number of pages	16
Journal	International Journal of Computational Geometry and Applications
Volume	9
Issue number	1
DOIs	https://doi.org/10.1142/S0218195999000078
State	Published - Feb 1999

Keywords

External visibility
Polygon
Shortest visible line segment
Weak visibility

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Theory and Mathematics
Computational Mathematics
Applied Mathematics

Access to Document

10.1142/S0218195999000078

Cite this

@article{9a277266338248f696750f4a64bbb114,

title = "Computing a shortest weakly externally visible line segment for a simple polygon",

abstract = "A simple polygon P is said to be weakly externally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of pq lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.",

keywords = "External visibility, Polygon, Shortest visible line segment, Weak visibility",

author = "Bhattacharya, {Binay K.} and Asish Mukhopadhyay and Toussaint, {Godfried T.}",

year = "1999",

month = feb,

doi = "10.1142/S0218195999000078",

language = "English (US)",

volume = "9",

pages = "81--96",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "1",

}

TY - JOUR

T1 - Computing a shortest weakly externally visible line segment for a simple polygon

AU - Bhattacharya, Binay K.

AU - Mukhopadhyay, Asish

AU - Toussaint, Godfried T.

PY - 1999/2

Y1 - 1999/2

N2 - A simple polygon P is said to be weakly externally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of pq lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.

AB - A simple polygon P is said to be weakly externally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of pq lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.

KW - External visibility

KW - Polygon

KW - Shortest visible line segment

KW - Weak visibility

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

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

U2 - 10.1142/S0218195999000078

DO - 10.1142/S0218195999000078

M3 - Article

AN - SCOPUS:0033484876

SN - 0218-1959

VL - 9

SP - 81

EP - 96

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 1

ER -

Computing a shortest weakly externally visible line segment for a simple polygon

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this