4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ "In other words, if n = number of vertices of l, the result should be l' = l" This is not compatible with the intersection requirement. In the example above, place the point somewhere inside the big dip to see why. $\endgroup$ – orlp Sep 9 '18 at 19:22
  • $\begingroup$ Yes, I realised this, but forgot to add a note here, sorry - I don't consider the lines to intersect if the line from p ends with the intersecting point (aka the lines form a "T" shape). Basically, l' = l is the optimum I want to achieve if there are enough vertices available - I just made a slight mistake defining the requirements. $\endgroup$ – user129186 Sep 9 '18 at 19:27
  • $\begingroup$ "I don't consider the lines to intersect if the line from p ends with the intersecting point." I don't see how that's relevant. Here's an example of the intersection: i.imgur.com/KPm4jMk.png. This clearly violates "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". $\endgroup$ – orlp Sep 9 '18 at 19:28
  • 1
    $\begingroup$ The definition of "covers" and "not behind" looks identical to me. What's the difference? Am I missing something? $\endgroup$ – D.W. Sep 10 '18 at 16:37
  • 1
    $\begingroup$ Can you edit the question to incorporate that assumption (the point $p$ will not be inside the convex hull of the poly line $l$)? $\endgroup$ – D.W. Sep 10 '18 at 16:41

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.