# Constructing a hyper-dimensional ball for a given point

I was wondering if a Julia package could help me out.

Suppose I have a point in two-dimension, for instance, [0,1] \times [0,1].

What I want to do is to construct a square centred at (0.1,0.3) with a distance d.

Then I want to collect random points inside the square.

This was doable, but once I started to generalize into n-dimension with multiple points, I got lost to
avoiding collecting overlapping points with each dimension’s box-constraint.

Would there be a package that I could look for?

Any suggestions would be greatly helpful.

Just to clarify: You want to draw random numbers from a n-dimensional (hyper-)square? Or do you want to make multiple squares and draw random points from their union (without giving more weight to potentially overlapping regions)?

Or something else?

1 Like

The latter is something that I want to do.

1 Like

Most straightforward way seems like drawing from the hyper-rectangle that contains all of them and then rejecting points that don’t belong to some rectangle in the collection. Probably inefficient in very high dimension but should work for lower dimensions. An additional optimization would be to partition into disjoint subsets of rectangles and choose a partition proportional to its volume. That would cut out a lot of empty rejection sampling space.

4 Likes

A variation on StefanKarpinski’s suggestion would be to choose a random hyperrectangle proportional to their volumes, draw a point p from that rectangle, then reject it with probability 1-1/nrect(p) where nrect(p) is the number of rectangles that contain p. This would save the effort of partitioning into disjoint hyperrectangles at the cost of requiring many rejections if nrect(p) becomes large.

Each of the proposed schemes is suitable for a different problem regime. I.e, which is best will depend on factors like the number of rectangles, the fraction of space occupied by rectangles, the amount of overlap in rectangles, etc.

4 Likes

Thank you very much to everyone!
I will try several programs and compare the running time.