Browse Prior Art Database

ON FINDING THE CONVEX HULL OF A SIMPLE POLYGON

IP.com Disclosure Number: IPCOM000128164D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

D~ T. Lee: AUTHOR [+3]

Abstract

In this paper we present a linear time algorithm for finding the convex hull of a simple polygon. Compared with the result of McCallum and Avi's [81 our algorithm requires only one stack, instead of two, and runs more efficiently.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON FINDING THE CONVEX HULL OF A SIMPLE POLYGON

D~ T. Lee Department of Electrical Engineering and Computer Science Northwestern University Evanston, Illinois 60201 U~S.A~

#80-03-FC-01

ABSTRACT

In this paper we present a linear time algorithm for finding the convex hull of a simple polygon. Compared with the result of McCallum and Avi's [81 our algorithm requires only one stack, instead of two, and runs more efficiently. On Finding the Convex Hull of a Simple Polygon D. T. Lee

Department of Electrical Engineering and Computer Science Northwestern University Evanston, Il 60201 U. S. A.

Key words: Convex hull, simple polygon, computational geometry, analysis of algorithms.

1. Introduction

One of the fundamental problems in computational geometry is that of finding the convex hull of a set of N points in k-dimensional space. Efficient and asymptotically optimal algorithms for the problem in 2- and 3-dimensional space are available [1, 2, 4, 5, 6, 9, 10, 11, 121. In this note we shall consider a special case of the problem in 2-dimen-sional space, i.e., the problem of finding the convex hull of a simple N edge polygon. The lower bound proof that determining the convex hull of N points requires L(N log N) time [3,, 10, 11) is no longer applicable in this case. In fact, a recent paper by McCallum and Avis [81 has shown that a linear time algorithm exists. Before this result is published, there are algorithms proposed by Sklansky [12) and by Shamos [111 which are claimed to be linear and which are proven incorrect afterwards. See Bykat (41 for a counterexample of Sklansky's algorithm. A slightly mod-ified counterexample of Shamos algorithm can also be constructed [8]. In this note we shall present and prove the validity of another linear time algorithm for this problem. In comparing the result of 18] our algorithm requires only one stack, instead of two, and runs more efficiently. We maintain that the stack T given in [8] is not that essential as indicated by McCallum and Avis and can be eliminated entirely.

2. Definitions and notations

A polygon is a closed plane figure with straight-line edges. A polygon is said to be.simple if no two nonadjacent edges of the polygon intersect. In what follows we shall denote a simple polygon P by a list of Vert ices, i.e.,

(Equation Omitted)

Northwestern University Page 1 Dec 31, 1980

Page 2 of 12

ON FINDING THE CONVEX HULL OF A SIMPLE POLYGON

such that

is an edge of P for

(Equation Omitted)

and the interior of the polygon lies to the left as the polygon is traversed. Each vertex v. is represented by its 3. x- and y-coordinates. We assume that no interior angle of the polygon is equal to 1800. The convex hull of P, denoted HULL (P), is the smallest convex polygon that contains P in its interior and is also represented by a list of some subset of the vertices of P. The hull vertices, accord- ing to the Jordan Curve Theorem, occur in sorted...