Path: utzoo!attcan!uunet!munnari.oz.au!metro!usage.csd.unsw.oz.au!usage.csd!lambert
From: lambert@spectrum.cs.unsw.oz.au (Tim Lambert)
Newsgroups: comp.theory
Subject: Re: comp. geometry
Message-ID: <LAMBERT.90Sep25234454@nankeen.spectrum.cs.unsw.oz.au>
Date: 25 Sep 90 13:44:54 GMT
References: <2473@dali>
Sender: news@usage.csd.unsw.oz.au
Organization: EE & CS, Uni of NSW, Australia
Lines: 17
In-reply-to: icsrc@nero.cs.montana.edu's message of 24 Sep 90 21:03:31 GMT

>>>>> On 24 Sep 90 21:03:31 GMT, icsrc@nero.cs.montana.edu (Rob Cimikowski) said:

> 2) Are there any good algorithms for finding a maximum set of
>    mutually equidistant points in 3 dimensions, that is, better than the
>    brute-force O(n**4) method of looking at all possible
>    subsets of 4 points?

For each point
   sort the other points by the distance to the selected point
   Check any triples that end up equidistant from the selected point

This is O(n^2log n).
I suppose you might get it down to O(n^2) with the right data
structure for the points, so that you could get the sorted distances
in linear time.

Tim