So I have been battling this rather peculiar problem:
given the following input (on an euclidean plane):
- point p
- polyline l
integer n
p is not inside of the convex hull of l
find a new polyline l', such that:
- it has n vertices
- it "covers" l with respect to p, i.e., a line section connecting any point on l with p will intersect l'
- it is not "behind" l with respect to p, i.e., a line section connecting any point on l' with p will not intersect l
- l' tries to approximate l as best as possible, even with the limited number of vertices n, it has, i.e., the maximum distance(l', any vertex on l) should be the smallest possible
In other words, if n = number of vertices of l, the result should be l' = l
I have drawn this sketch for better illustration with two different examples. The point p is drawn in green, the line l in black and l' in blue.
In layman's terms, I want to create a simplified version of the polyline by "pushing" a new polyline with a predefined number of vertices onto it, from the direction of the point. The new polyline cannot under any circumstances get to the other side of the old polyline.
The definition of "covers" is there in order to make sure that l' is not "smaller" from the point of view of p. As in, imagine you were standing at point p. You should not be able to see l, you should only be able to see l'. The difference is that "covers" is a line, but "is behind" is a line section. I guess they are basically the same, but I wanted to make it clear what I want to achieve.
I would like to find a fast optimization algorithm for this, provided this is polynomial-time solvable (it feels like it, right?). I was thinking linear programming, but I have no idea how to formulate the problem. I am of course open to any other ideas.
Any help would be greatly appreciated!
A few note about the two examples I posted in the comments:
Left vol, cell 4: As you can see, l has this large "valley". This is where l gets the farthest from p. The objective is for l' to close in on this distance as much as it can, with the limited number of vertices it has (n=4), without violating any of the constraints. The first and last points are where they are to satisfy the "cover" constraint and because it's the closest possible. The third point from left: it gets as close as possible, without violating the "behind" constraint (if it was any lower down, the lines would intersect on top right, below the second point of l, from right).
Right column illustration. This is a bit of a mistake on my part. The first point on the right is not exactly supposed to be where it is in this illustration. It is supposed to be there tho demonstrate the "covers" constraint, but it basically does not make sense with p being where it is in the illustration. Basically, Imagine that p is way farther to the top (i did not want to make a tall drawing). If its farther to the top, the right point of l' needs to extend over l like this, in order to satisfy the "covers" constraint.
