Recognition and searching of one-sided polygons
| dc.contributor.advisor | Keil, J. Mark | en_US |
| dc.contributor.committeeMember | Eramian, Mark G. | en_US |
| dc.contributor.committeeMember | Cheston, Grant A. | en_US |
| dc.contributor.committeeMember | Peng, Jian | en_US |
| dc.creator | Zhang, Zhichuan | en_US |
| dc.date.accessioned | 2008-01-18T16:09:03Z | en_US |
| dc.date.accessioned | 2013-01-04T04:24:14Z | |
| dc.date.available | 2008-01-21T08:00:00Z | en_US |
| dc.date.available | 2013-01-04T04:24:14Z | |
| dc.date.created | 2008-01 | en_US |
| dc.date.issued | 2008-01-21 | en_US |
| dc.date.submitted | January 2008 | en_US |
| dc.description.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. | en_US |
| dc.identifier.uri | http://hdl.handle.net/10388/etd-01182008-160903 | en_US |
| dc.language.iso | en_US | en_US |
| dc.subject | polygon search problem | en_US |
| dc.subject | One-sided | en_US |
| dc.title | Recognition and searching of one-sided polygons | en_US |
| dc.type.genre | Thesis | en_US |
| dc.type.material | text | en_US |
| thesis.degree.department | Computer Science | en_US |
| thesis.degree.discipline | Computer Science | en_US |
| thesis.degree.grantor | University of Saskatchewan | en_US |
| thesis.degree.level | Masters | en_US |
| thesis.degree.name | Master of Science (M.Sc.) | en_US |