Recognition and searching of one-sided polygons
Date
2008-01-21
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
Type
Degree Level
Masters
Abstract
In this thesis, we discuss a new kind of polygon, which we call one-sided polygons. The shortest path between any pair of vertices of a one-sided polygon makes only left turns or right turns. We prove that the set of one-sided polygons is a superset of the star-shaped polygons and the spiral polygons. We also show that the set of one-sided polygons is a subset of the set of LR-visibility polygons. We present a linear time recognition algorithm for one-sided rectilinear polygons. We then discuss the searching of monotone and one-sided rectilinear polygons. We show that all one-sided polygons can be 1-searched and a search schedule can be given in linear time.
Description
Keywords
polygon search problem, One-sided
Citation
Degree
Master of Science (M.Sc.)
Department
Computer Science
Program
Computer Science