New answers tagged cg.comp-geom
2
Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post.
Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are standard, to the end.
Here is the first lemma. Most likely this is already in the Monma and Suri paper.
Given any bipartition $(C_1, C_2)$ of $G$,
let $W(C_1, ...
1
If you rotate your rectangles through a common origin, then your method works.
Your method works if there always exists a separating line that is parallel to a side of one of your rectangles. Such a line indeed exists. To see this, start from an arbitrary separating line and rotate it until it hits both rectangles, say in vertices $p$ and $q$.
For a given ...
Top 50 recent answers are included