Finding the convex hull of a simple polygon |
| |
Authors: | Ronald L Graham F Frances Yao |
| |
Institution: | Bell Laboratories, Murray Hill, New Jersey 07974 USA;Xerox Palo Alto Research Center, Palo Alto, California 94304 USA |
| |
Abstract: | It is well known that the convex hull of a set of n points in the plane can be found by an algorithm having worst-case complexity O(n log n). A short linear-time algorithm for finding the convex hull when the points form the (ordered) vertices of a simple (i.e., non-self-intersecting) polygon is given. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |