Register to reply

Point packing problem

by EvoG
Tags: packing, point
Share this thread:
EvoG
#1
Apr25-14, 01:11 PM
P: 1
I have a problem and I'm not sure if it has been formulated and/or solved before.

Suppose you have a finite n-dimensional space in which each dimension is constrained to [0,1]. I need the maximum number of points p that can be put in this space such that no two points are closer than some threshold t.

For instance, if n = 2 and t = 1, then p = 4. Think of the corners of a square with sides of length 1.
If n = 2 and t = 1.4, then p = 2, since opposite corners of a square with sides of length 1 are > 1.4 distance apart.

In general, my n is going to be large (>10000) and my t will certainly be greater than 1. I don't need a perfect formula. An approximation that gets me to within a factor of about 2 of the actual solution would be good enough.

I suspect this problem may be reducible to the sphere packing problem which has only been solved for up to 8 dimensions, but I thought I'd check with the experts to see.
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
mathman
#2
Apr25-14, 02:44 PM
Sci Advisor
P: 6,112
It does look like a sphere packing problem with radius = t/2.
Mark44
#3
Apr25-14, 03:10 PM
Mentor
P: 21,409
Quote Quote by mathman View Post
It does look like a sphere packing problem with radius = t/2.
Except for at the corners and edges of the enclosing "box".

HallsofIvy
#4
Apr25-14, 05:19 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,691
Point packing problem

But since the "t" is minimum possible distance, the corners not really relevant. Using spheres of radius t/2 should give the same result as using cubes with side length t.
mathman
#5
Apr26-14, 03:17 PM
Sci Advisor
P: 6,112
Quote Quote by HallsofIvy View Post
But since the "t" is minimum possible distance, the corners not really relevant. Using spheres of radius t/2 should give the same result as using cubes with side length t.
I don't think so. Using cubes will fill up the box neatly. Spheres will pack more tightly.


Register to reply

Related Discussions
Geometry Problem involving packing Hexagons into Circles Differential Geometry 1
Operational research : Shelf packing problem Calculus & Beyond Homework 4
Packing Problem General Math 11
Sphere packing problem General Math 7
Volume problem - Closest packing Introductory Physics Homework 4