University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

      Recognition and searching of one-sided polygons

      Thumbnail
      View/Open
      zhichuan.pdf (1.087Mb)
      Date
      2008-01-21
      Author
      Zhang, Zhichuan
      Type
      Thesis
      Degree Level
      Masters
      Metadata
      Show full item record
      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.
      Degree
      Master of Science (M.Sc.)
      Department
      Computer Science
      Program
      Computer Science
      Supervisor
      Keil, J. Mark
      Committee
      Eramian, Mark G.; Cheston, Grant A.; Peng, Jian
      Copyright Date
      January 2008
      URI
      http://hdl.handle.net/10388/etd-01182008-160903
      Subject
      polygon search problem
      One-sided
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      The University of Saskatchewan's main campus is situated on Treaty 6 Territory and the Homeland of the Métis.

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy