A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

Godfried T. Toussaint

doi:10.1016/0167-8655(86)90043-7

A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

Godfried T. Toussaint

Computer Science

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

Abstract

A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.

Original language	English (US)
Pages (from-to)	449-451
Number of pages	3
Journal	Pattern Recognition Letters
Volume	4
Issue number	6
DOIs	https://doi.org/10.1016/0167-8655(86)90043-7
State	Published - Dec 1986

Keywords

Weak visibility
computer geometry
computer graphics
shortest paths
strong hidden-line problem
triangulation

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0167-8655(86)90043-7

Cite this

@article{619f239dac604072967ca6a140572577,

title = "A linear-time algorithm for solving the strong hidden-line problem in a simple polygon",

abstract = "A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.",

keywords = "Weak visibility, computer geometry, computer graphics, shortest paths, strong hidden-line problem, triangulation",

author = "Toussaint, {Godfried T.}",

note = "Funding Information: This research was supported by grants FCAC-EQ1678, NSERC-A9293 and a Killam Senior Research Fellowship from the Canada Council.",

year = "1986",

month = dec,

doi = "10.1016/0167-8655(86)90043-7",

language = "English (US)",

volume = "4",

pages = "449--451",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

AU - Toussaint, Godfried T.

N1 - Funding Information: This research was supported by grants FCAC-EQ1678, NSERC-A9293 and a Killam Senior Research Fellowship from the Canada Council.

PY - 1986/12

Y1 - 1986/12

N2 - A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.

AB - A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.

KW - Weak visibility

KW - computer geometry

KW - computer graphics

KW - shortest paths

KW - strong hidden-line problem

KW - triangulation

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

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

U2 - 10.1016/0167-8655(86)90043-7

DO - 10.1016/0167-8655(86)90043-7

M3 - Article

AN - SCOPUS:0022872173

SN - 0167-8655

VL - 4

SP - 449

EP - 451

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 6

ER -

A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this