2
$\begingroup$

I've heard of packing problems in general, and I've seen a couple questions on this site that address specific cases (e.g. how to pack 45-45-90 triangles into an arbitrary shape), but after a search I think mine is different enough to be worth posting. Also perhaps this doesn't technically qualify as packing, but it's in the same vein.

For context, I'm working on this project where I'm designing a satellite. I have a map of the locations with clear sky on the Earth and I want to figure out where I should point my satellite to maximize the area covered.

To be precise, I have a collection of polygons that are not necessarily connected, which all together represent the clear area. I have the ability to pick $n$ (say 30) points, around which I will draw a square-like shape (it's not exactly square due to the Earth's curvature). How do I pick my points so that I maximize the area covered by my satellite?

  • The coverage of the red squares inside the green is what I want to optimize .

enter image description here

The reason this may not count as packing is that I'm not trying to fit the squares strictly inside the shape, I'm just trying to cover as much of it as possible.

What I've tried:

  • Pick random points, then use some iterative method like the genetic algorithm to adjust the positions of squares. The issue with this is that you end up with some points that are stuck on tiny bits of clear land, where there are larger clear spots further away. Also this often (from experience, but I could be doing it wrong) results in more overlap of squares than is ideal. Overlap is acceptable in small amounts, since I'm trying to maximize unique area covered, so if I have to overlap squares a little bit to do that, it's okay.
  • Create a fixed lattice of points, and pick the $n$ points with the highest amount of clear area inside. This works fine, just not great, and I want to make it better. I've thought about trying to shift the lattice in a couple different directions, but then if it makes certain squares better it might make others worse.

Also this is somewhat CS"-ey" question, and maybe counts as research-level, so please let me know if I should post this elsewhere, but I'm curious about this problem in general. Is there some general method to find the best way to pack arbitrary shapes into a larger arbitrary shape? Hopefully this isn't too vague or anything, and if it is I'd be happy to clarify, this is my first question so take it a bit easy on me!

link to the image

$\endgroup$
  • $\begingroup$ Nice question (+1), the picture enclosed. $\endgroup$ – user376343 Mar 14 at 21:08
  • 1
    $\begingroup$ @user376343 Thanks! $\endgroup$ – C. McCracken Mar 14 at 21:30

Your Answer

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

Browse other questions tagged or ask your own question.