1
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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$:

enter image description here

Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.