Award Date

1-1-1995

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

Number of Pages

36

Abstract

Two problems dealing with visibility in the interior of a polygon are investigated. We present a linear time algorithm for computing the stair-case visibility polygon from a point inside a simple polygon, which is optimal within a constant factor. We show that the problem of locating the minimum number of 90{dollar}\sp\circ{dollar}-flood-lights to illuminate the interior of a simple polygon is NP-complete. We also discuss the generalization of the above results.

Keywords

Polygons; Properties; Visibility

Controlled Subject

Computer science

File Format

pdf

File Size

1003.52 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Identifier

https://doi.org/10.25669/5cc7-tqfo


Share

COinS