Recognition and searching of one-sided polygons

View/ Open
Date
2008-01-21Author
Zhang, Zhichuan
Type
ThesisDegree Level
MastersMetadata
Show full item recordAbstract
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.
Degree
Master of Science (M.Sc.)Department
Computer ScienceProgram
Computer ScienceSupervisor
Keil, J. MarkCommittee
Eramian, Mark G.; Cheston, Grant A.; Peng, JianCopyright Date
January 2008Subject
polygon search problem
One-sided