Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!maverick.ksu.ksu.edu!ux1.cso.uiuc.edu!kadie
From: kadie@cs.uiuc.edu (Carl M. Kadie)
Newsgroups: comp.graphics
Subject: Re: Finding nearest point
Message-ID: <kadie.666638061@herodotus.cs.uiuc.edu>
Date: 15 Feb 91 17:14:21 GMT
References: <kadie.666468082@herodotus.cs.uiuc.edu>
Sender: news@ux1.cso.uiuc.edu (News)
Organization: University of Illinois at Urbana
Lines: 18

In <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes:

>Given a set of 3-D data points, {<x,y,z>}, and
>a point p1, <x1,y1,z1>, is there a fast way to find which
>point in the set is nearest to p1?

>I've tried to think of ways to sort the set, but search is
>linear (and often a little slower).

I've received many helpful replies. Many people
recommend the book "Computational Geometry" by Preparata
and Shamos. And a book by Herbert Edelsbrunner.

(Coincidental, Preparata and  Edelsbrunner have offices upstairs
of mine)
 
--
Carl Kadie -- kadie@cs.uiuc.edu -- University of Illinois at Urbana-Champaign