Browse Prior Art Database

A: NEW REAL-TIME ALGORITHM FOR THE TWO`:-DIMENSIONAL CONVEX HULL PROBLEM

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

Publishing Venue

Software Patent Institute

Related People

Edmond Schonberg: AUTHOR [+4]

Abstract

We present a new real-time algorithm for the determination of the convex hull of a set of points in the plane. Being real-time, this algorithm has the same complexity as that of Preparata [lj, i.e. each new point is processed in time 0(log N) where N is the number of points already on the convex hull. The method we use is akin to that of [lj, but has a simpler geometric structure, and has the advantage of discarding internal points more efficiently. Both algorithms achieve their real-time behaviour by means of an efficient procedure to determine whether a point P is internal or external to a simple convex polygon C, which is the convex hull of a set S of points in the plane.

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

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A: NEW REAL-TIME ALGORITHM FOR THE TWO`:-DIMENSIONAL CONVEX HULL PROBLEM

by Edmond Schonberg and Zhiying Zhou

SEPTEMBER 1981 REPORT NO. A new real-time algorithm for the two-dimensional convex hull problem.

Zhiying Zhou* and Edmond Schonberg Courant Institute of Mathematical Science New York University

Keywords: analysis of algorithms, complexity, computational geometry.

We present a new real-time algorithm for the determination of the convex hull of a set of points in the plane. Being real-time, this algorithm has the same complexity as that of Preparata [lj, i.e. each new point is processed in time 0(log N) where N is the number of points already on the convex hull. The method we use is akin to that of [lj, but has a simpler geometric structure, and has the advantage of discarding internal points more efficiently. '

Both algorithms achieve their real-time behaviour by means of an efficient procedure to determine whether a point P is internal or external to a simple convex polygon C, which is the convex hull of a set S of points in the plane.

i) If P is internal to C, then the convex hull of S + {P} is C.

ii) Otherwise, let vt, vt' be points on C such that the lines Pvt and Pvt are supporting lines for C
(i.e. C lies fully on one side of each line). Then the convex hull of S+{P} consists of one of the sequences of vertices of G from vt to vt' (the sequence which is farther from P) together with the paint P. In what follows we call vt, vt' the tangent points from P. * Permanent Address : Tsinghua University, Peking, China. _2_

Our method for the efficient determination of the tangent points (if they exist) is based on the following simple observation:

Let v designate a point on C, which moves around C (in counterclockwise order, say) and consider the ray Pv. -

a) If P is internal to C, then the ray Pv sweeps 27r. as v describes the perimeter of C. Furthermore, we can find three vertices i,j,k on C such that the angles

(Equation Omitted)

are less than n and counterclokwise. (Fig. 1)

b) If P is external to C, then the ray PV will rotate counterclockwise on some segment of C, and clockwise on the rest of C (Fig.2). Furthermore, the vertices at which the rotation of Pv changes polarity are precisely the tangent points. This suggests a modified binary search method for determining their existence and position. The outline of the algorithm is as follows

New York University Page 1 Dec 31, 1981

Page 2 of 6

A: NEW REAL-TIME ALGORITHM FOR THE TWO`:-DIMENSIONAL CONVEX HULL PROBLEM

1. Choose three points

(Equation Omitted)

on C. (we will see later how to make the initial choice of these points).

2. If the angles

(Equation Omitted)

have the same polarity, then P is internal to C.

3. Otherwise, let

(Equation Omitted)

be some circular permutation of

(Equation Omitted)

such that iPj has a different polarity from jPk. Then one of the tangent points may be between i and k.

3.1 If

(Equa...