I have many dots on a plane, e.g. $(1,1), (3,5), (5,9)$. Imagine each dot is a country. Now I define each country should at least occupy an area of $100$ unit square.(width: 10 unit, height: 10 unit) No dots should be sitting on other dots' occupied area.
So I need an algorithm to rearrange the position of these dots, so that they won't sit within others' area.
Any thoughts?
There are many ways to generate $n$ squares of size $d \times d$ on a plane. Here is the most straightforward approach:
Take the Cartesian $xy$ coordinate plane, and in specific the positive $x$-axis. Divide the $x$-axis into the following intervals: $$ I _i = \left\{x = (i-1)\times d \dots i \times d \right\}\qquad i = 1, 2, 3, \dots , n $$ In other words, slice the axis, starting from $0$, into $n$ intervals of length $d$. The interval $i$ serves as the base of square number $i$.
The squares $S_i$ are generated from these intervals $I_i$ only by defining that the height is $d$: $$ S_i = \text{set of points $(x,y)$ so that $x\in I_i$ and $0 \leq y\leq d$} $$ Can you visualize the squares now? The centre points of the squares are easy to calculate, they are $$ C_i = (x,y) = \left(i+\frac{d}{2}, \frac{d}{2} \right) $$