Structured visibility profiles with applications to problems in simple polygons

Paul J. Heffernan; Joseph S.B. Mitchell

Structured visibility profiles with applications to problems in simple polygons

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

9 Scopus citations

Abstract

A number of problems in computational geometry involving simple polygons can be solved in linear time once the polygon has been triangulated. Since the worst-case time bound for triangulating a general simple polygon is currently super-linear, these algorithms are not linear time in the worst case. In this paper we define the structured visibility profile of a polygonal path and show how to compute it in linear time. We apply this result to solve many problems in linear time that previously required triangulation. Our list of problems includes: translation separability of two simple polygons, computing the weak visibility region for a segment within a simple polygon, finding shortest monotone paths in a simple polygon, ray shooting from an edge, and the convex rope problem.

Original language	English
Title of host publication	Proc Sixth Annu Symp Comput Geom
Publisher	Publ by ACM
Pages	53-62
Number of pages	10
ISBN (Print)	0897913620
State	Published - 1990
Event	Proceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA Duration: Jun 6 1990 → Jun 8 1990

Publication series

Name	Proc Sixth Annu Symp Comput Geom

Conference

Conference	Proceedings of the Sixth Annual Symposium on Computational Geometry
City	Berkeley, CA, USA
Period	06/6/90 → 06/8/90

Cite this

@inproceedings{504a8ef3e5514d56ab5183bbb1677d03,

title = "Structured visibility profiles with applications to problems in simple polygons",

abstract = "A number of problems in computational geometry involving simple polygons can be solved in linear time once the polygon has been triangulated. Since the worst-case time bound for triangulating a general simple polygon is currently super-linear, these algorithms are not linear time in the worst case. In this paper we define the structured visibility profile of a polygonal path and show how to compute it in linear time. We apply this result to solve many problems in linear time that previously required triangulation. Our list of problems includes: translation separability of two simple polygons, computing the weak visibility region for a segment within a simple polygon, finding shortest monotone paths in a simple polygon, ray shooting from an edge, and the convex rope problem.",

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

year = "1990",

language = "English",

isbn = "0897913620",

series = "Proc Sixth Annu Symp Comput Geom",

publisher = "Publ by ACM",

pages = "53--62",

booktitle = "Proc Sixth Annu Symp Comput Geom",

note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",

}

TY - GEN

T1 - Structured visibility profiles with applications to problems in simple polygons

AU - Heffernan, Paul J.

AU - Mitchell, Joseph S.B.

PY - 1990

Y1 - 1990

N2 - A number of problems in computational geometry involving simple polygons can be solved in linear time once the polygon has been triangulated. Since the worst-case time bound for triangulating a general simple polygon is currently super-linear, these algorithms are not linear time in the worst case. In this paper we define the structured visibility profile of a polygonal path and show how to compute it in linear time. We apply this result to solve many problems in linear time that previously required triangulation. Our list of problems includes: translation separability of two simple polygons, computing the weak visibility region for a segment within a simple polygon, finding shortest monotone paths in a simple polygon, ray shooting from an edge, and the convex rope problem.

AB - A number of problems in computational geometry involving simple polygons can be solved in linear time once the polygon has been triangulated. Since the worst-case time bound for triangulating a general simple polygon is currently super-linear, these algorithms are not linear time in the worst case. In this paper we define the structured visibility profile of a polygonal path and show how to compute it in linear time. We apply this result to solve many problems in linear time that previously required triangulation. Our list of problems includes: translation separability of two simple polygons, computing the weak visibility region for a segment within a simple polygon, finding shortest monotone paths in a simple polygon, ray shooting from an edge, and the convex rope problem.

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

M3 - Conference contribution

AN - SCOPUS:0024983593

SN - 0897913620

T3 - Proc Sixth Annu Symp Comput Geom

SP - 53

EP - 62

BT - Proc Sixth Annu Symp Comput Geom

PB - Publ by ACM

T2 - Proceedings of the Sixth Annual Symposium on Computational Geometry

Y2 - 6 June 1990 through 8 June 1990

ER -

Structured visibility profiles with applications to problems in simple polygons

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this