Nearest Neighbor Points
Gil Israel Winograd
least one nearest neighbor. What is the maximum number of points that any
given point can claim to be the nearest neighbor of, and what
configuration of points yields this result?
What about the same question in x-y-z space?
What about 2nd nearest points?
Is there a generalization to n-space and mth nearest points?
-* Gil
Glenn Rhoads
>Consider a series of points in the x-y plane. Each of these points has at
>least one nearest neighbor. What is the maximum number of points that any
>given point can claim to be the nearest neighbor of, and what
>configuration of points yields this result?
Six. The six neighbors form a regular hexagon and the given point is at
the center of the hexagon. (An appropriate picture and a simple argument
suffice to show this but I can't draw the picture in ascii.)
>What about the same question in x-y-z space?
Don't Know. It would be nice if the neighboring points formed a platonic
solid (someone can check this out). My brain doesn't reliably handle 3-D.
>What about 2nd nearest points?
No idea.
>Is there a generalization to n-space and mth nearest points?
Ouch! If there is, it is beyond my abilities to determine.
-- Glenn Rhoads
Kris Popat
In article <4ikqk5$9...@elaine26.Stanford.EDU> Gil Israel Winograd
writes:
> Consider a series of points in the x-y plane. Each of these points has
> at least one nearest neighbor. What is the maximum number of points
> that any given point can claim to be the nearest neighbor of, and what
> configuration of points yields this result?
> What about the same question in x-y-z space?
Regarding the maximum number, the following paper gives an upper bound
that significantly improves on the best previously known upper bound:
| AUTHOR: Zeger, Kenneth; Gersho, Allen
| CORP SOURCE: Dept. of Electr. Eng., Illinois Univ., Urbana, IL, USA
| TITLE: Number of nearest neighbors in a Euclidean code
| SOURCE: IEEE Transactions on Information Theory, vol.40, no.5,
| p. 1647-9
Kris Popat
MIT Rm. E15-391 Cambridge MA 02139
Ross Millikan
g...@leland.Stanford.EDU (Gil Israel Winograd) writes:
> Consider a series of points in the x-y plane. Each of these points has at
> least one nearest neighbor. What is the maximum number of points that any
> given point can claim to be the nearest neighbor of, and what
> configuration of points yields this result?
Six, with the points at the center and corners of a hexagon (if ties
are
permitted. The center point is the closest point to all the others.
If
the angle between two points as seen from the cneter point is less than
60 degrees, they will be closer to each other than to the center.
>
> What about the same question in x-y-z space?
Twelve, hexagonal close pack. I'm not sure this is proved, but
everybody
knows it's true
>
> What about 2nd nearest points?
Probably the same, due to the large number of ties.
> Is there a generalization to n-space and mth nearest points?
Of course, but it's beyond me
Ross Millikan
robert a. moeser
rho...@sceloporus.rutgers.edu (Glenn Rhoads) wrote:
:g...@leland.Stanford.EDU (Gil Israel Winograd) writes:
:
:>Consider a series of points in the x-y plane. Each of these points has at
:>least one nearest neighbor. What is the maximum number of points that any
:>given point can claim to be the nearest neighbor of, and what
:>configuration of points yields this result?
:
:Six. The six neighbors form a regular hexagon and the given point is at
:the center of the hexagon. (An appropriate picture and a simple argument
:suffice to show this but I can't draw the picture in ascii.)
:
:
:>What about the same question in x-y-z space?
:
:Don't Know. It would be nice if the neighboring points formed a platonic
:solid (someone can check this out). My brain doesn't reliably handle 3-D.
the point at the center of an icosahedron is the closest neighbor
to 12 points at the icosa's vertices.
in a dodecahdron, the vertices are closer together than the distance
to the center, so this won't work.
-- rob
Darren Rigby
Glenn Rhoads <rho...@sceloporus.rutgers.edu> wrote:
>g...@leland.Stanford.EDU (Gil Israel Winograd) writes:
>
>>Consider a series of points in the x-y plane. Each of these points has at
>>least one nearest neighbor. What is the maximum number of points that any
>>given point can claim to be the nearest neighbor of, and what
>>configuration of points yields this result?
>Six. The six neighbors form a regular hexagon and the given point is at
>the center of the hexagon. (An appropriate picture and a simple argument
>suffice to show this but I can't draw the picture in ascii.)
>
>>What about the same question in x-y-z space?
>
>Don't Know. It would be nice if the neighboring points formed a platonic
>solid (someone can check this out). My brain doesn't reliably handle 3-D.
>
as above. Then set up two more hexagons, each of which share the same two
points from the original, such that the planes these new hexagons are in are
offset 60 degrees from the original, one in each direction.
\ /
--*--
/ \ So the planes look like this. Our center point is on the line
through the center of the star, pointing straight out of your
screen. Closest to you on that line is one of the two points shared by
all three hexagonal configurations (septunxes?). All of the points not
on that line form another pair of hexagons (centerless) that lie in planes
which are parallel to your screen. Is this distance less than that to
the center?
If so, then you can certainly get away with ten, two septunxes in perp-
endicular planes: |
-+-
|
>
>>What about 2nd nearest points?
>
>No idea.
>
>>Is there a generalization to n-space and mth nearest points?
>Ouch! If there is, it is beyond my abilities to determine.
>-- Glenn Rhoads
Don't look at me.
--
djr={gridby, dart, axoq}
Darren Rigby
Kris Popat <po...@media.mit.edu> wrote:
>
>In article <4ikqk5$9...@elaine26.Stanford.EDU> Gil Israel Winograd
>
>> Consider a series of points in the x-y plane. Each of these points has
>> at least one nearest neighbor. What is the maximum number of points
>> that any given point can claim to be the nearest neighbor of, and what
>> configuration of points yields this result?
>
>
>that significantly improves on the best previously known upper bound:
>
>| AUTHOR: Zeger, Kenneth; Gersho, Allen
>| CORP SOURCE: Dept. of Electr. Eng., Illinois Univ., Urbana, IL, USA
>| TITLE: Number of nearest neighbors in a Euclidean code
>| SOURCE: IEEE Transactions on Information Theory, vol.40, no.5,
>| p. 1647-9
>
>Kris Popat
>MIT Rm. E15-391 Cambridge MA 02139
That's very interesting. What's the answer they give?
Glenn Rhoads
>>least one nearest neighbor. What is the maximum number of points that any
>>given point can claim to be the nearest neighbor of, and what
>>configuration of points yields this result?
>Six. The six neighbors form a regular hexagon and the given point is at
>the center of the hexagon. (An appropriate picture and a simple argument
>suffice to show this but I can't draw the picture in ascii.)
I think I can describe the picture and argument well enough to convince
someone.
Start with the given point and call it A. Add a point, called P1, so that
A is its nearest neighbor. Obviously, P1 can be added anywhere. For sake
of argument, add P1 to the right of A. I.e. the coordinates of A are (0,0)
and the coordinates of P1 are (x,0) with x>0. (For simplicity don't draw
the coordinate axis; they aren't needed and just clutter up the diagram.)
Consider where you can add another point, P2, so that A is a nearest
neighbor to both P1 and P2. Draw the perpendicular bisector of A and P1.
P2 cannot be placed to the right of this line or else P2's nearest neighbor
would be P1 not A. Draw a circle centered at P1 with A on the circumference.
(I.e. radius is x = the distance between P1 and A). P2 cannot be inside
of this circle or else P1's nearest neighbor would be P2 not A. Draw rays
from A to the two intersection points of the circle with the perpendicular
bisector. P2 cannot be placed anywhere inside the pie-shaped wedge formed
by these two rays. The angle P1,A, and a ray is 60 degrees. Therefore,
no matter where a nearest neighbor to A is, there can be no other nearest
neighbors within 60 degrees of that point. Since there are 360 degrees
around A, at most six nearest neighbors can be placed around A. The
configuration described previously shows that A can indeed have six
neighbors and hence this is the maximum. In fact, this configuration is
unique. P2 can be placed anywhere that is not to the right of the
perpendicular bisector nor inside the circle. The only position that P2
can be placed that doesn't form an angle (with A and P1) of more than
60 degrees is precisely at an intersection of the circle and the
perpendicular bisector. We can then repeat the process and add a point P3.
By the same argument, there are unique locations where P3 can be placed
so that it doesn't eliminate more than 60 degrees around A for the location
of the succeeding point. Once we have placed point P1, the placement of
all the succeeding points will be uniquely determined. Hence, the
configuration is unique.
With the aid of a diagram, I hope the above is clear.
-- Glenn Rhoads
Stephen H. Landrum
>
> In article <4inbmt$h...@sceloporus.rutgers.edu>,
> Glenn Rhoads <rho...@sceloporus.rutgers.edu> wrote:
> >g...@leland.Stanford.EDU (Gil Israel Winograd) writes:
> >>
> >
> >solid (someone can check this out). My brain doesn't reliably handle 3-D.
> >
> I think you can only get away with 14. Start with the six in a hexagon pattern
> as above. Then set up two more hexagons, each of which share the same two
> points from the original, such that the planes these new hexagons are in are
> offset 60 degrees from the original, one in each direction.
>
> \ /
> --*--
> / \ So the planes look like this. Our center point is on the line
> through the center of the star, pointing straight out of your
> screen. Closest to you on that line is one of the two points shared by
> all three hexagonal configurations (septunxes?). All of the points not
> on that line form another pair of hexagons (centerless) that lie in planes
> which are parallel to your screen. Is this distance less than that to
> the center?
Only the two outside points that common to all three planes have the
center point as their nearest neighbor. The other points have closer
neighbors than the center point.
>
> If so, then you can certainly get away with ten, two septunxes in perp-
> endicular planes: |
> -+-
> |
In fact, it is easy to show that 12 points can be achieved - consider
13 identically sized spheres arranged so that 12 surround and touch
the interior one, and the points in question are the centers of the
spheres. I think that 12 points is the maximum that can be achieved
in 3-space, but if I am wrong there is some evidence in nature that
14 would be the next candidate. Masses of approximately equal sized
bubbles tend to form 14 sided polyhedra
> >
> >>What about 2nd nearest points?
> >
> >No idea.
> >
> >>Is there a generalization to n-space and mth nearest points?
> >Ouch! If there is, it is beyond my abilities to determine.
> >-- Glenn Rhoads
> Don't look at me.
If there is a generalization to n-space, it is probably closely related
to n-sphere packing.
--
Stephen H. Landrum voice: (415)261-2626 email: slan...@3do.com
System software programmer, M2 graphics division.
For general 3DO questions email customer...@3do.com
Kris Popat
From the Zeger and Gersho paper I cited in my earlier post, the cases
that are known are:
dimension max number
1 2
2 6 (as Rhoads points out)
3 12 (as Moeser points out)
8 240
24 196560
For other dimensionalities, my understanding is that only bounds, not
exact values, are known. Good upper and lower bounds for low
dimensionality appear in:
J. Conway and N. Sloane, "Sphere packings, lattices, and
groups," Springer-Verlag, 1988.
The Zeger and Gersho bound in the paper I cited earlier was for
arbitrarily high-dimensional space.
Kris Popat
MIT Rm. E15-391 Cambridge, MA 02139
Douglas J. Zare
>[...]
>In fact, it is easy to show that 12 points can be achieved - consider
>13 identically sized spheres arranged so that 12 surround and touch
>the interior one, and the points in question are the centers of the
>spheres. I think that 12 points is the maximum that can be achieved
>in 3-space, but if I am wrong there is some evidence in nature that
>14 would be the next candidate. Masses of approximately equal sized
>bubbles tend to form 14 sided polyhedra
(tetrakaidecahedra, in case anyone uses an electronic search)
Puzzle: Design an experiment that would allow one to test this.
This question was asked by Kelvin. Various results and papers in the last
few years suggest that the answer should be less than 14. One group that I
worked in, under the direction of Peter Norman and Robert Kusner, tried an
experiment which gave a value of about 13.5 . I think the data was
tainted, though...
Douglas Zare
http://www.cco.caltech.edu/~zare
Courtenay Footman
In 1991, Hsiang claimed to have proved that the upper limit was 24
in four dimensions. Does anyone know if that result is considered
valid? For that matter, is his proof of the Kepler sphere packing
problem valid?
24 is the number of nearest neighbors in a body centered hypercube.
--
-------------------------------------------------------------------------------
Courtenay Footman I have again gotten back on the net, and
c...@lightlink.com again I will never get anything done.
Bill Shera
In a previous article, g...@leland.Stanford.EDU (Gil Israel Winograd) says:
>Consider a series of points in the x-y plane. Each of these points has at
>least one nearest neighbor. What is the maximum number of points that any
>given point can claim to be the nearest neighbor of, and what
>configuration of points yields this result?
Well, you could n points with n-1 points arranged in a circle with one
point at it's center. Then, you could have your central point claim an
infinite number of nreaest neighbor points.
>
>What about the same question in x-y-z space?
>
You could also put this two-dimensional circle into 3D space, or rotate
it into a sphere. This shouldn't really give you any more points
(infinity=infinity=infinity), but it'll look cooler.
Unless the point of this exercise is to find some kind of optimal "tile"
type arrangement, which can be extrapolated into an embdment space of n
dimensions. If that's the case, I vote for the
square-cum-cube-cum-tesseract-..., unless there's an arrangement of
hexagons that works better (odds are there is).
With a slightly different perspective, I'm...
--
Effervescently yours,
Bill Shera
aka
Bones the Wunderslug, screaming it out from the DarXide!
Glenn Rhoads
>>Consider a series of points in the x-y plane. Each of these points has at
>>least one nearest neighbor. What is the maximum number of points that any
>>given point can claim to be the nearest neighbor of, and what
>>configuration of points yields this result?
>Well, you could n points with n-1 points arranged in a circle with one
>point at it's center. Then, you could have your central point claim an
>infinite number of nreaest neighbor points.
Nope. The nearest neighbor to a point on the circle would be also be on
the circle instead of the central point. The previously posted responses
are correct.
>>What about the same question in x-y-z space?
>>
>You could also put this two-dimensional circle into 3D space, or rotate
>it into a sphere. This shouldn't really give you any more points
>(infinity=infinity=infinity), but it'll look cooler.
Same mistake again.
Also, all infinities are *NOT* equal. I can't explain it in a single post
plus I don't know if you have the necessary mathematics background to
follow such an explanation. Anyway, you can try looking up the Theory of
Transfinite Numbers which was developed by Cantor about 100 years ago.
[text deleted]
-- Glenn Rhoads
Carl Witthoft
>Consider a series of points in the x-y plane. Each of these points has at
>least one nearest neighbor. What is the maximum number of points that any
>given point can claim to be the nearest neighbor of, and what
>configuration of points yields this result?
>
Can I use the discrete metric? :=)
It might be interesting to compare Euclidean and "box" metrics, tho'.
--
Carl Witthoft @ Adaptive Optics Associates
ca...@aoainc.com 54 CambridgePark Drive, Cambridge,MA 02140 617-864-0201
" Axis-navigo, ergo sum."
Douglas J. Zare
>>bubbles tend to form 14 sided polyhedra
>>[...]
>(tetrakaidecahedra, in case anyone uses an electronic search)
>
>Puzzle: Design an experiment that would allow one to test this.
Historically, people have done such things as compressing lead shot or
peas. Another possibility was to freeze shaving-cream. People doubt the
accuracy of the first model, although it made the data easy to document.
The latter has too much liquid, so the gas bubbles are not pushed against
each other enough.
We froze 500 water balloons compressed together and lubricated so that
they could slip past each other. One idea was that we could quickly draw
the edges on the balloons after taking them out, and that this would
allow leisurely tabulation. Instead, we discovered that the stretch marks
sufficed.
However, we also found that ice crystals are sharp enough to pop water
balloons, especially when these are forced together tightly. Perhaps a
tenth of the balloons burst, but we weren't sure at what stage.
Suggestions?
Douglas Zare
http://www.cco.caltech.edu/~zare