Let's say I use some green chalk to draw and fill a continous shape on a chalkboard. Let's assume the shape has no holes in it.
I then use some red chalk to cover the area around my blob for a sufficient distance around my blob.
Let's say I then have a chalkboard eraser of height h. Its width is negligible.
To "erase" is defined as moving the eraser over the chalkboard in any direction (I understand some ambiguity is introduced by purely vertical movement if I'm assuming the width is negligible. In the end, for the larger problem, I'd have to consider non-negligible widths, so I'm allowing purely vertical movement now). "Erasing" any point removes the chalk from that point. If I go over a point with the eraser, it's "eraser count" is 1.
For any vertical cross-section of my blob, the height of the cross-section could range from a single point up to several times h.
I have two rules: My eraser must always be vertical, but I can move it in the x and y dimensions freely. Once I put the eraser against the board, I can't pick it up again until I am done ("done" based on maximizing and minimizing rules below). The motion should be continuous in the x and y directions.
I would like to maximize:
- The amount of green chalk I erase.
I would like to minimize:
The amount of red chalk I erase.
The standard deviation of the "eraser count" of the set of points that have an eraser count >0, and were green originally. (Because of the rule about not being able to pick the eraser up, you would end up having to go over some areas more than once for backtracking, or to grab some horizontal strip that's <h high. I would like to equalize the number of times any area is 'erased' compared to any other area.)
For areas of red chalk, I would like to minimize the eraser count somehow. Not sure how to define this any further than that (lowest maximum, lowest average or median, lowest std dev like above?).
I would say the priority of these statemens is the priority that they are listed. I recognize the difficulties or impossibility of attempting to optimize too many things.
My questions are:
Does this type of problem have a name, or seem analagous to any other problem type? The only thing I could think of (as a layman) was tiling problems.
Does an algorithm for something like this already exist? Searches for "chalkboard eraser" or "paint roller" algorithms didn't get me anywhere.
What are some keywords I can look up, or areas of further study? Basically, like, what is this? What am I trying to talk about here?
Am I making this too complicated? Is there an approach that is obvious that can be supported as optimal or near optimal?
(I recognize there are a number of things going on here and I thank you for your patience. I am not a mathematician, and have only undergraduate education in math (up through differential equations) This is my attempt at a generalized explanation of a real world problem I am working on, and the constraints of that have influenced the rules above. I hope I have explained it clearly enough. Anyone who could say "well, if you get rid of all of your constraints except #X and the rule about A, then it sounds like such and such," please do so. Much appreciated.)