6
$\begingroup$

I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below.

Paths through a tunnel or sequence of polygons

Initially my interest was limited to the set containing discrete curves with the possible smallest segment count and within this set the discrete curve with the shortest length. I've been able to find this discrete curve (not shown in the above graphic).

Now I'm considering the problem of the straightest-possible discrete curve that can be embedded in the polygon, and I suspect, or rather I'm hoping, that both curves, the one with the smallest segment count and the straightest one are identical. I'd appreciate help showing that is or isn't the case.

Note: I'm aware of the concept of geodesics as shortest possible paths. However, the curve I'm studying isn't the shortest path but the path with the smallest segment count. In the example provided above, the shortest path would cut around corners as it seeks to minimize the path length. Interestingly, this curving of the path increases its segment count.

Clarification of the question (courtesy of arex)

Suppose a simple polygon is given, along with two points, s and t, within the polygon. Is there a polygonal path from s to t that simultaneously minimizes the number of segments and amount of turning. Simple means homeomorphic to a disk; a polygonal path is a piecewise-linear curve; and turning is measured by the sum of the absolute values of the turning angles.

I'm making the following restatement of the initial problem, now solved, because it describes the sort of path that I'm investigating. Also the description may trigger insight into the question of bounds on straightness:

The polygon can be considered as a tunnel in which there is no line of sight between two points, which we can imagine to be the source and destination of a light beam. We seek to install the smallest number of light beam relays required to forward a signal as quickly as possible though the tunnel from source to the destination. The locations of the relays are the equivalent to the intermediate vertices of the shortest discrete curve with the minimum possible segment count embeddable in a non-trivial/non-convex polygon.

Improve this question
$\endgroup$
40
  • 3
    $\begingroup$ By a "path of polygons" it sounds like you mean "a polygon". Is that correct? Is it correct that you are asking whether there is a path that simultaneously minimizes the number of segments and also minimizes the sum of the absolute value of angles? $\endgroup$
    – Bill Thurston
    Commented Jan 12, 2011 at 14:20
  • 2
    $\begingroup$ @Dmitri: No I am not asking about the shortest path through a graph. If anything, Patrick's diagram makes that abundantly clear. (A shorter curve can have a larger segment count.) In the language of graphs, I am interested in the path with the smallest node count or hops, which in the original problem domain amounts to the curve with the smallest segment count. As to whether this question is best suited to MO, I can only say that it is a computational geometry question which makes it acceptable in MO. I have therefore taggged it as such. Like Patrick I welcome a formal proof of your assertion. $\endgroup$
    – Olumide
    Commented Jan 12, 2011 at 19:09
  • 4
    $\begingroup$ @Dmitri Pavlov: I find your eagerness to close impossible to understand. If it's so obvious, can you at least tell us the answer? Does there always exist a path that simultaneuously minimises the number of straight-line segments and the 'straightness'? $\endgroup$
    – TonyK
    Commented Jan 12, 2011 at 19:35
  • 2
    $\begingroup$ @Dmitri Pavlov: I don't think I have violated the intent of the original poster: I have just clarified it. Can you answer my question? I did say 'please'. I don't mind if you can't, but I wish you would admit it :-) $\endgroup$
    – TonyK
    Commented Jan 12, 2011 at 21:29
  • 8
    $\begingroup$ Please stop arguing in this comment thread. Protracted arguments about the suitability of a question belong on meta. If you ever find yourself wanting to "argue back", please post a link to meta instead. $\endgroup$
    – Kim Morrison
    Commented Jan 12, 2011 at 22:43

2 Answers 2

Reset to default
4
$\begingroup$

As a complement to Bill Thurston comment, what situation do you prefer?

http://math.huji.ac.il/~piz/private/Image1.png

In the second case you have more segments but the length is shorter, and obviously the sum of the angles are equal in both cases.

Note: I assume that the ends points are fixed, that is you have no choice on their position on the side of the polygon. Is it OK?

P.S. I couldn't put the figure in the comment, so I put it in an answer even if it is not, it was to long to explain with words.

Addendum:

I am not sure that the process of simplification can help in anything. But I'll try to clarify what I have in mind. Imagine that the bold black curve is the path of minimal length (I didn't draw the ambient polygon). You go from $a$ to $b$ etc. The point $b$ is the first point of "inflection", means that the turning changes sign. If you don't touch the first and last segments on $(a,b)$ you will not change the total turning angle on this piece of path. You have then (on the picture) the choice of three simplifications (thin lines marked with circles at rupture points), two of them gain 1 segment count, and the other one gains 2. If some of them fit in the ambient polygon, it's fine, and you continue that way, on the next part, until the next inflection point. You would like to simplify also by shortcutting along the green dashed line, but you cant since the bold curve is assumed to be the shortest, it must be an obstacle there. So, this way starting with a short curve you may improve the straightness. As I am really not an expert on this kind of geometry, I am not sure this way leads somewhere. It seems that there is still a long way from here to a proof of the existence of what you are looking for.

http://math.huji.ac.il/~piz/private/Image2.png

Improve this answer
$\endgroup$
26
  • $\begingroup$ This is an perspective on the domain of solutions. I'd naively assumed that a curve with a longer segment count not be as straight but your figure shows that this is possible. The question now therefore is if a straighter curve exists. My primary interest is in determining if the curve with smallest number of segments is (one of) the straightest possible. In which case, no other curve, regardless of segment count, can be straighter. I hope this makes sense. $\endgroup$
    – Olumide
    Commented Jan 12, 2011 at 16:02
  • $\begingroup$ I'm not sure what it means that a curve would increase the segment count as is currently stated in the question. It would be possible to join the beginning and end points of the path in this example with a semicircle, or in the second example by a quarter circle in such a way that there would be no corners ie tangent continuously defined at every point. How is a segment defined in such a case? I'm confused as to what is being asked, and how straightness is being defined. $\endgroup$
    – Mark Bennet
    Commented Jan 12, 2011 at 19:45
  • $\begingroup$ @Mark The curve is made of concatenate affine segments. The "straightness" is defined as the sum of the absolute values of the "turning angles" (the curvatures). Note that, on each convex/concave part of the curve the straightness is just the difference of the angles at the two ends (measured correctly) and the total straightness is the sum of the partial straightness on these elementary sub-curves. It seems that the question is to find an algorithm to minimize the straightness and the segments count simultaneously. $\endgroup$
    – Patrick I-Z
    Commented Jan 12, 2011 at 21:03
  • $\begingroup$ @Patrick What I seem to be confused about is whether curves are allowed. If we are talking about line segments that is clear. The curves are longer than the segments, but I was not sure whether the segments were straighter than the curves (or as straight as - I think the quarter-circle in the second example is as straight as the segments shown on the definition given, but it is smooth in the sense of having a continuously varying tangent, and I was not sure whether this would make the configuration a single segment when assessing the segment count) $\endgroup$
    – Mark Bennet
    Commented Jan 12, 2011 at 21:20
  • 1
    $\begingroup$ BTW both picture links in your answer seem to be dead. (Uploading picture through the editor should create more stable link - an imgur link posted through Stack Exchange account.) I'm just mentioning this since the question has been bumped anyway. $\endgroup$
    – Martin Sleziak
    Commented Jun 10, 2017 at 5:34
4
$\begingroup$

The natural generalization of your "straightest-possible" constraint is a curvature-constrained path. I know this is not what you asked, but I wanted to mention that even finding a path with maximum curvature 1 inside a convex polygon is already difficult. This was studied by Agarwal et al. in a paper, "Curvature-Constrained Shortest Paths in a Convex Polygon," (SIAM Journal on Computing, Volume 31, Issue 6, 2002) Here is one of their figures, which hints at why it is difficult to find a path between initial $I$ and final $F$ positions/orientations:
Fig5

Returning to the question (or questions) you did ask, I think looking at the paper "Polygonal path simplification with angle constraints," by Chen et al. (Computational Geometry, Volume 32, Issue 3, November 2005, Pages 173-187), might help. They explicitly consider the "tunnel" version of your revised question, phrased in terms of an error tolerance $\epsilon$. Perhaps most usefully for your purposes, they describe all the related work in this domain, which has considered many variations. Usually those variations start with a path $P$, and then try to find another path (a "simplification") with certain properties: (1) The min-# problem: Find a path that remains within $\epsilon$ of $P$ but has the fewest segments; (2) The min-$\epsilon$ problem: Given a fixed number $m$ of segments, find a path using no more than $m$ segments that minimizes $\epsilon$. This specific paper solves the min-# problem with the addition of angular constraints, which seems close to your initial formulation (as clarified in the comments).

Edit. Here is a preliminary version of the "Simplification" paper: simplification.pdf.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Unfortunately, the paper is not free :( $\endgroup$
    – Patrick I-Z
    Commented Jan 12, 2011 at 21:36
  • $\begingroup$ Sorry about that, Patrick. I added a link to a preliminary version. $\endgroup$
    – Joseph O'Rourke
    Commented Jan 12, 2011 at 21:55
  • 2
    $\begingroup$ The paper shows that the question seems far to be trivial, and the method of simplification for a given path may work (although I am not a specialist of this kind of geometry). It seems to me that there are two parts for solving this kind of questions: the first part would be to guess the good candidates to be simplified, and the point here could be: where to put the inflection points? The second part would consist to the simplification, which seems more feasible algorithmically. I know that this cannot help much. But now, the ball is in the court of the specialists :-) $\endgroup$
    – Patrick I-Z
    Commented Jan 12, 2011 at 22:25
  • $\begingroup$ The link to sciencedirect.com is broken, but the article can be found at doi:10.1016/j.comgeo.2004.09.003 (Zbl 1082.65018). $\endgroup$
    – The Amplitwist
    Commented May 8, 2023 at 17:40
  • 1
    $\begingroup$ The link to cs.smith.edu also seems to be broken at the moment, but a copy of the PDF is saved at the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented May 8, 2023 at 17:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .