icsrc@nero.cs.montana.edu (Rob Cimikowski) (09/25/90)
A couple of questions for computational geometers: 1) Given a set of points in 3-dimensional space, what is the maximum number which can be mutually equidistant? (is it 4?) Can the answer be generalized for n dimensions? 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? If any algorithms are known, I would appreciate references. Thanks, Bob Cimikowski Montana St Univ icsrc@caesar.cs.montana.edu
odevil@mirsa.inria.fr (Olivier Devillers,L025,657763) (09/25/90)
From article <2473@dali>, by icsrc@nero.cs.montana.edu (Rob Cimikowski): > A couple of questions for computational geometers: > > 1) Given a set of points in 3-dimensional space, what is the maximum > number which can be mutually equidistant? (is it 4?) Can the answer > be generalized for n dimensions? Yes, given a mutually equidistant set of d points in dim d-1, (it is a regular simplex) now in dimension d, any point to increase the set must yields on the intersection of all the spheres centered on one of the points and passing through toe others, There is exactly two intersection points for these spheres, any of these two points may be choosen, but not the two because their mutual distance are not good > > 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? If the problem is to find a mutually equidistant points, with no other closest points, such a set corresponds to a vertex of the Voronoi diagram, and can be found in O(n**2) worst case (O(n log n) for any realistic data) It is also possible to use the order less than k Voronoi diagrams if you suppose than their is at most k points closest to the set (then the complexity is O(n**2 k**2) ) Otherwise, I can't see good solutions, but of course, you can detect all the T equilateral triangles in time O(n**3) and find all regular tetrahedra in time O(nT) which can be better than O(n**4) In other words, you can found all the mutually equidistant sets in output sensitive time (in any dimension) _ __ __ ___ __ __ __ __ Tel:+33 93657763 / / / / | / / /_ /_/ / / /_ | / / / / /_ /_/ /_ Telex: 970 050F /_/ /__ / |/ / /__ / \ _/_/ /__ |/ / /__ /__ /__ / \ __/ Fax:+33 93657765 INRIA - 2004 Route des Lucioles - 06565 VALBONNE CEDEX (France) odevil@alcor.inria.fr
lambert@spectrum.cs.unsw.oz.au (Tim Lambert) (09/25/90)
>>>>> 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