**comp.graphics.algorithms**

## Subject: **Re: A Geometry Problem**

"Vector"

news:1145068978.245417.13290@e56g2000cwe.googlegroups.com...

> Give a set of points in 3D Space {Vi: 1 = 1,2,...,n}, find the point

> Va, a (- {1,2,...,n} to minimize

>

> distance = sum||Va-Vi||

> i=1,..n

>

> to design a O(n^2)algorithm is easy , is there fast algorighm, for

> example O(n*logn)

See "Computational Geometry: An Introduction", by

F. P. Preparata and M. I. Shamos, Springer-Verlag.

Section 5.4 is on "The Closest Pair Problem: A

Divide-and-Conquer Approach".

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

A Geometry Problem =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.