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
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
mathman
#2
Apr25-14, 02:44 PM
Sci Advisor
P: 6,059
It does look like a sphere packing problem with radius = t/2.
Mark44
#3
Apr25-14, 03:10 PM
Mentor
P: 21,265
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,510
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,059
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