A counterexample to an algorithm for computing monotone hulls of simple polygons |
| |
Authors: | Godfried T. Toussaint Hossam El Gindy |
| |
Affiliation: | School of Computer Science, McGill University, Montreal, P.Q., Canada H3A 2K6 |
| |
Abstract: | A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on . In this note we show that the first step does not always work correctly and can even yield non-simple polygons, invalidating the use of the second step. It is also shown that the first step can discard convex hull vertices thus invalidating the use of any convex hull algorithm in the second step. |
| |
Keywords: | Convex hull monotone hull maximal polygons simple polygons weakly externally visible polygons algorithms complexity computational geometry pattern recognition |
本文献已被 ScienceDirect 等数据库收录! |