Browse Prior Art Database

Algorithm for Finding Nearest points in Convex Hulls

IP.com Disclosure Number: IPCOM000082921D
Original Publication Date: 1975-Feb-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 75K

Publishing Venue

IBM

Related People

Wolfe, PS: AUTHOR

Abstract

The present nearest-point algorithm has immediate application to a variety of optimization problems, and its application to the separation of two point sets has widespread application to pattern recognition problems. While other procedures have been used for such problems, it is believed that the present one is more flexible and efficient.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 3

Algorithm for Finding Nearest points in Convex Hulls

The present nearest-point algorithm has immediate application to a variety of optimization problems, and its application to the separation of two point sets has widespread application to pattern recognition problems. While other procedures have been used for such problems, it is believed that the present one is more flexible and efficient.

Let P(1),...,P(m) be points in R/n/ (Euclidean n-space). The subject procedure is an efficient means of determining that point; X = Sigma/m/ P(j)w(j) (with Sigma(j) w(j) = 1, all w(j) > - = 0) in the convex hull of the given point set having smallest Euclidean norm Absolute X/2/.

At any stage of the algorithm there is at hand, the set of s indices S Approximately Equal{1,..,m} such that the point set {P(j) : j Epsilon S) is affinity independent that is, the equations X =

Sigma(j Epsilon S) P(j)w(j),(j Epsilon S) w(1) = 1 have for any X in R/n/. Below P[S] denotes the n-by-s matrix whose columns are {P(j) : j Epsilon S}, w denotes an s-vector, and e denotes the s-vector all of whose components are 1.

THE ALGORITHM Step 0. Defining J by Absolute P(J)/2/ = Min {Absolute P(j) /2/, j=1,..,m}, set S = {J} and w = (1).

Step 1. (a) Set X = P[S]w. (b) Define J by X/T/P(J) = Min {S(T)PJ, all j}.

(c) If X/T/P(J) > X/T/X - Z(1) {Max Absolute P(j)/2/ :

j Epsilon S(u){(J)}}, STOP (see Note 1).

(d) If J Epsilon S then STOP (Note 2).

(e) If not stopped above, then replace S by S(u){J} and

w by (w,O).

Step 2. (a) Solve the equations

(Image Omitted)

(b) If v > Z(2)e (Note 3), set w = v and go to Step
1. Otherwise,

Step 3. (a) Let POS...