Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!simard From: simard@cs.rochester.edu Newsgroups: comp.theory Subject: closest point to a polygone Message-ID: <1989Nov27.060304.27985@cs.rochester.edu> Date: 27 Nov 89 06:03:04 GMT Sender: simard@cs.rochester.edu (Patrice Simard) Organization: University of Rochester Computer Science Department Lines: 21 Help, 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 where A is an m by n matrix, X is an n-dimensional vector, and B and 0 are of dimension m. The (inelegant) solution I have now is to find a point of M using the simplex method and then do some kind of gradient descent (O((mn)^2)) to find the closest point to P. Any help would be appreciated. -- Patrice (simard@cs.rochester.edu) ps: Any information about where to get C code to do this will be welcome (also if you have a good C program for simplex...). Brought to you by Super Global Mega Corp .com