Recognition and searching of one-sided polygons

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.