Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We have given convex polygon of $N$ vertices, and two circles of radius $r$. Is it possible to check if we can place those two circles completely inside the polygon, such that they don't intersect, but they might have one point in common.
For example if we have given square with sides of length $1$, and $r = 0.25$. Then the answer should be yes, as we can place those two circles.
Let $P$ be the given polygon. Let $Q$ be the set of points inside $P$ whose distance to the boundary of $P$ is at least $r$. Your requirement can be met iff the diameter of $Q$ is at least $2r$. Indeed a radius $r$ circle lies inside $P$ iff its center is in $Q$, and two such circles are disjoint iff the distance between their centers is at least $2r$.
The problem of finding $Q$ is called inward polygon offsetting. That link has a lot of discussion about the general case, but it should be much simpler when $P$ is convex.
Suppose the vertices of $P$ are $p_1,\ldots,p_n$ in counterclockwise order. Let $R$ denote rotation counterclockwise by $90^\circ$. Let $n_i$ be the outward unit normal vector to edge $p_ip_{i+1}$, namely $n_i=R(p_i-p_{i+1})/|R(p_i-p_{i+1})|$. Let $e_i$ denote this edge shifted by $r$, namely the line from $p_i-rn_i$ to $p_{i+1}-rn_i$. Now we can iteratively construct a path $q$ which will become the boundary of $q$. In iteration $1$, let $q=e_1$. In iteration $i$, find the intersection of $q$ with $e_i$, discard the part of $q$ after the intersection and append the part of $e_i$ after the intersection (we should look for the intersection starting from the end of $q$; the more segments we have to check, the more vertices we can discard, so the algorithm will still be $O(n)$). After $n$ iterations, find where $q$ intersects itself and discard excess vertices to obtain a closed path; this is the boundary of $Q$.
Once we have $Q$, we can find its diameter using the Rotating calipers algorithm.
