# Tag Info

3

This problem has been studied in the 1980's. You can find it named the problem of finding a minimum rectangle partition of an orthogonal polygon with holes. In the older literature, sometimes "orthogonal" is replaced with "rectilinear." If you wrap your black rectangles with the minimum bounding box, then you have converted it to an orthogonal polygon with ...

3

This is an instance of what is generally known as the Point in Polygon problem. Assuming all your vertex coordinates are integral, you essentially want to find out if (-0.5, 0.5) or (0.5,0.5) are on the interior of the polygon. One thing you need to do is decide on how you will deal with complicated cases like loops in the polygon edge. The usual course ...

2

Maybe you can take some ideas from the following paper RAPPAPORT, David. A convex hull algorithm for discs, and applications. Computational Geometry, 1992, 1.3: 171-187. where you model each sheep with a circle of radius $d$. However the paper does not directly solve your problem because the convex hull described in the paper is composed by line segments ...

Only top voted, non community-wiki answers of a minimum length are eligible