Finding a nonredundant component in a polygon
Bradley Howard Coleman · Summit (Simon Fraser University) · 2011
Let v i be a reflex vertex (internal angle greater than π) of a polygon P with n vertices.Extend the clockwise edge of v i as a ray until it hits P , and then walk clockwise from v i to the hitpoint.The chain we walked defines the clockwise component of v i (it also has a counterclockwise component).In O(n) time we find some component of P that does not entirely contain another component, without using a general O(n) time triangulation algorithm.This time bound has already been achieved using such a triangulation algorithm, but we show it is possible without it.Our central algorithm simultaneously walks a component in the clockwise and counterclockwise directions.In these walks, it shoots rays and finds acceptable hitpoints that are not necessarily correct.For a particular hitpoint, the algorithm either validates it, disqualifies it and finds another, or shoots a new ray and finds a finds a new hitpoint.