I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (external intersection meaning if the point is not contained in the interior of the union of all the squares).
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$:
Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).
