Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Robust Point Location in Approximate Polygons

Robust Point Location in Approximate Polygons

File(s)
91-1208.ps (768.65 KB)
91-1208.pdf (563.93 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7048
Collections
Computer Science Technical Reports
Author
Stewart, A. James
Abstract

This paper presents a framework for reasoning about robust geometric algorithms. Robustness is formally defined and a data structure called an approximate polygon is introduced and used to reason about polygons constructed of edges whose positions are uncertain. A robust algorithm for point location in an approximate polygon is presented. The algorithm uses only the signature of the point (not its location) to determine whether the point is inside or outside the polygon. An approximate polygon could, by shifting its edges back and forth within their error bounds, induce a large number of different line arrangements. The cell $C_{a}$ with signature $\alpha$ in one such arrangement will be different than the cell ${C'}{a}$ with signature $\alpha$ in another arrangement. This paper proves that, regardless of their position and shapes, the cells $C{a}$ and ${C'}_{a}$ are always to the same side of the polygons which induce their respective arrangements.

Date Issued
1991-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1208
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance