# Jordan Curve Theorem: Application to Path Crossing Obstacles ## (i) Obstacles are Convex Polygons Suppose there are $n$ convex obstacles in the plane, with a start point $S$ and a goal point $G$ in the free space. Let $k$ be the number of times the straight-line segment $SG$ crosses the boundaries of the obstacles. ### Lower Bound on $k$ - **Lower Bound:** $k = 0$ - **Explanation:** This occurs if the segment $SG$ does not intersect any obstacle boundary at all. - **Example Sketch:** - All obstacles are placed away from the line segment $SG$, so $SG$ is completely in the free space. - _[Imagine a line segment from S to G with all convex obstacles far away from the segment; no intersection occurs.]_ ### Upper Bound on $k$ - **Upper Bound:** $k = 2n$ - **Explanation:** The straight line can cross each convex obstacle at most twice (entering and exiting). This is a property of convex sets: a straight line can intersect the boundary of a convex region in at most two points. - **Example Sketch:** - Arrange all $n$ convex obstacles so that $SG$ passes through all of them, entering and exiting each. - _[Imagine a series of non-overlapping convex obstacles aligned along $SG$, so $SG$ passes through each one, entering and exiting: $n$ obstacles $\times$ 2 crossings each = $2n$ intersections.]_ --- ## (ii) Obstacles are Arbitrary Polygons with 5 Edges (Pentagons) Suppose now the $n$ obstacles are arbitrary (possibly non-convex) polygons, each with exactly 5 edges. ### Lower Bound on $k$ - **Lower Bound:** $k = 0$ - **Explanation:** As above, if $SG$ misses all obstacles, $k = 0$. ### Upper Bound on $k$ - **Upper Bound:** $k = 5n$ - **Explanation:** For a general (possibly non-convex) polygon with $m$ edges, a straight line can cross the boundary up to $m$ times (one for each edge, if arranged accordingly). For $n$ pentagons, $5n$ is the maximum number of crossings. - **Example Sketch:** - Arrange each pentagon so that $SG$ crosses all 5 edges (e.g., a highly non-convex "star" shaped pentagon, or overlapping pentagons). - _[Imagine $n$ pentagons placed so that $SG$ enters and exits at every edge; for each pentagon, $SG$ crosses 5 times, for a total of $5n$.]_ --- ## Summary Table | Obstacle Type | Lower Bound $k$ | Upper Bound $k$ | |---------------|-----------------|-----------------| | Convex | $0$ | $2n$ | | 5-gon | $0$ | $5n$ | --- **Note:** - The Jordan Curve Theorem ensures that every simple closed curve divides the plane into an inside and outside region, which is why a crossing must alternate between those regions. - For convex obstacles, the segment can only enter and exit once (2 crossings max per obstacle). - For arbitrary polygons, more crossings are possible due to non-convexity, up to the number of edges per obstacle.