Zur schnellen Zerlegung von Polygonen in sternförmige Polygone. (On fast decomposition of polygons into star-shaped polygons) (Q811139)

The paper studies visibility of a simple polygon P from its vertices. By a result of Chvátal, each boundary point of P is visible from at least one vertex in a suitably chosen subset T containing n/3 of the n vertices of P. Moreover, T can be calculated in time O(n log n). As shown in the paper, O(n) time suffices for finding T provided P is r-convex, that is, the polygon formed by the reflex vertices of P is convex. In addition, upper bounds on the cardinality of T are given for simply polygons with h holes and a total of n vertices. One needs at most \(1/3(n+2h)\) vertices in the general case and at most \(1/4(n+2h)\) vertices when the polygon and its holes are axis-parallel.