Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!brutus.cs.uiuc.edu!rpi!image.soe.clarkson.edu!sunybcs!sbcs!kepler1!rjfrey From: rjfrey@kepler1.UUCP (Robert J Frey) Newsgroups: comp.theory Subject: Re: closest point to a polygone Message-ID: <164@kepler1.UUCP> Date: 27 Nov 89 21:57:32 GMT References: <1989Nov27.060304.27985@cs.rochester.edu> Reply-To: rjfrey@kepler1.UUCP (Robert J Frey) Organization: Kepler Financial Mgmt, Setauket, NY Lines: 22 In article <1989Nov27.060304.27985@cs.rochester.edu> simard@cs.rochester.edu writes: > >I'm looking for an algorithm which given a point P and and a convex polygone M >in a n-dimentional space S, find the closest point of M to P. The convex >M is given by the set of m linear constraints: > > A X + B > 0 > The square distance between the variable X and the fixed point P is a quadratic function of X; your problem is the quadratic program (QP): minimize (X1-P1)^2 + (X2-P2)^2 + ... + (Xn-Pn)^2 subject to X in M This is easy to solve. Consult any intro text in Operations Research. -- Dr. Robert J Frey, Kepler Financial Management, Ltd. {acsm, lilink, polyof, sbcs}!kepler1!rjfrey *or* frey@sbcs.sunysb.edu voice: (516) 689-6300 * fax: (516) 751-8678 Brought to you by Super Global Mega Corp .com