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
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
mathman
#2
Apr25-14, 02:44 PM
Sci Advisor
P: 6,077
It does look like a sphere packing problem with radius = t/2.
Mark44
#3
Apr25-14, 03:10 PM
Mentor
P: 21,312
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,568
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,077
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