Kvant Math Problem 161

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m36s
Source on kvant.digital

Problem

A lake has the shape of a non-convex $n$-gon. Prove that the set of points in the lake from which all its shores are visible is either empty or fills the interior of a convex $m$-gon, where $m\le n$.

I. N. Bernstein

Exploration

Let the lake be the interior of a simple nonconvex polygon $P=A_1A_2\cdots A_n$.

A point $X$ sees a point $Y$ of the shore if the segment $XY$ lies entirely in the lake together with its endpoint $Y$. The condition that all shores are visible means that every point of the boundary of $P$ is visible from $X$. Since each side of the polygon is a segment, it is enough that every point of every side be visible.

For a convex polygon every interior point sees the whole boundary. For a nonconvex polygon this fails because a reflex vertex creates an obstruction. Consider a polygon with one indentation. The points from which the whole boundary is visible form a convex region near the center. This suggests that the desired set is an intersection of several half-planes.

Take a side $A_iA_{i+1}$. If $X$ sees every point of that side, then $X$ and the interior of the polygon must lie on the same side of the line $A_iA_{i+1}$. For an ordinary edge this condition is automatically satisfied by every point of the polygon. The interesting constraints come from reflex vertices.

A more useful viewpoint is the standard kernel of a polygon: the set of points from which every point of the polygon is visible. For a simple polygon, the kernel is the intersection of the half-planes bounded by the edge lines and containing the interior locally adjacent to each edge. The kernel is convex. Since the boundary is contained in the polygon, every point of the kernel sees all shores.

The converse requires care. If a point sees all shores, does it see every interior point? Take an interior point $Y$. Since the polygon is simple, every ray from $X$ through $Y$ meets the boundary at some point $Z$ beyond $Y$. If $X$ sees all boundary points, then $XZ\subset P$. Because $Y$ lies on the segment $XZ$, the segment $XY$ also lies in $P$. Hence $X$ sees every interior point. Thus the set of points seeing all shores coincides with the kernel.

The crucial point is proving this converse rigorously. Once established, the result follows from the classical half-plane description of the kernel. The number of sides of the resulting convex polygon is at most $n$, because it is obtained as the intersection of at most $n$ half-planes.

Problem Understanding

The lake is the interior of a simple nonconvex polygon with $n$ sides. We must prove that the set of points of the lake from which every point of the shoreline is visible is either empty or is exactly the interior of a convex polygon having at most $n$ sides.

This is a Type B problem. The statement itself is to be proved.

The core difficulty is to identify the visibility set with a geometric object whose structure is easy to analyze. The natural candidate is the kernel of the polygon, namely the set of points from which every point of the polygon is visible. One must prove that seeing the entire shoreline already implies seeing the whole polygon.

Proof Architecture

Let $K$ denote the set of points of the lake from which every point of the shoreline is visible.

First, prove that $K$ coincides with the kernel of the polygon. The inclusion from the kernel to $K$ is immediate because the shoreline belongs to the polygon. For the reverse inclusion, take a point $X\in K$ and an arbitrary interior point $Y$; extend the ray $XY$ until it meets the boundary at a point $Z$, then use the visibility of $Z$ to deduce the visibility of $Y$.

Next, describe the kernel as an intersection of half-planes. For each side of the polygon, consider the closed half-plane bounded by the line containing that side and containing the interior of the polygon near that side. A point belongs to the kernel exactly when it lies in all these half-planes.

Then show that an intersection of half-planes is convex. Hence the kernel is convex.

Finally, show that the intersection of at most $n$ half-planes is either empty or a convex polygon with at most $n$ sides. Since $K$ equals the kernel, the desired statement follows.

The hardest part is the proof that visibility of the whole shoreline implies visibility of every interior point.

Solution

Let $P$ be the polygon forming the boundary of the lake, and let $K$ be the set of points of the lake from which every point of the shoreline, that is, every point of $\partial P$, is visible.

We first prove that $K$ is exactly the kernel of the polygon.

Let $L$ denote the kernel of $P$, namely the set of points $X\in P$ such that for every point $Y\in P$, the segment $XY$ is contained in $P$.

Since $\partial P\subset P$, every point of $L$ sees every point of the shoreline. Hence

$$L\subseteq K.$$

Now let $X\in K$. We shall prove that $X\in L$.

Take an arbitrary point $Y\in P$. If $Y\in\partial P$, then $XY\subset P$ by the definition of $K$.

Assume that $Y$ lies in the interior of $P$. Consider the ray starting at $X$ and passing through $Y$. Since $P$ is bounded, this ray eventually leaves $P$. Let $Z$ be the first point of intersection of the ray with the boundary $\partial P$ beyond $Y$.

The segment $XZ$ lies entirely in $P$, because $X$ sees every boundary point and in particular sees $Z$. Since $Y$ belongs to the segment $XZ$, the segment $XY$ is contained in $XZ$, hence also contained in $P$.

Thus every point $Y\in P$ is visible from $X$. Therefore $X\in L$.

We have proved

$$K=L.$$

It remains to describe $L$.

For each side $e$ of the polygon, let $H_e$ be the closed half-plane bounded by the line containing $e$ and containing points of the interior of the polygon adjacent to that side.

We claim that

$$L=\bigcap_e H_e.$$

Suppose first that $X\in L$. Let $e$ be any side of the polygon. If $X\notin H_e$, then $X$ lies on the opposite side of the line containing $e$. Choose a point $Y$ in the relative interior of $e$. The segment $XY$ crosses the supporting line of $e$ at $Y$ and approaches $Y$ from the exterior side of the polygon. Consequently, points of $XY$ arbitrarily close to $Y$ lie outside $P$, contradicting $X\in L$. Hence $X\in H_e$ for every side $e$, and therefore

$$X\in\bigcap_e H_e.$$

Conversely, suppose that

$$X\in\bigcap_e H_e.$$

Take any point $Y\in P$. If some point of the segment $XY$ lay outside $P$, then moving from $X$ toward $Y$ along the segment, there would be a first point at which the segment leaves the polygon. At such a point the segment would cross a side line from the interior side to the exterior side. This is impossible because both endpoints $X$ and $Y$ belong to the half-plane $H_e$ associated with that side, and a segment joining two points of a convex half-plane remains entirely in that half-plane.

Hence $XY\subset P$ for every $Y\in P$, which means that $X\in L$.

Thus

$$L=\bigcap_e H_e.$$

Since every half-plane $H_e$ is convex, their intersection is convex. Therefore $L$, and hence $K$, is convex.

The intersection involves exactly $n$ half-planes, one for each side of the polygon. An intersection of finitely many half-planes is either empty or a convex polygonal region. Each side of its boundary lies on one of the supporting lines of the original polygon, so the resulting polygon has at most $n$ sides.

Therefore the set of points from which all shores of the lake are visible is either empty or the interior of a convex $m$-gon with

$$m\le n.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the implication from visibility of the shoreline to visibility of every interior point. Let $X$ see every boundary point and let $Y$ be interior. The ray from $X$ through $Y$ meets the boundary at a point $Z$ beyond $Y$. Since $X$ sees $Z$, the whole segment $XZ$ lies in the polygon. The point $Y$ belongs to this segment, so $XY\subset XZ\subset P$. The argument uses only the existence of the boundary point $Z$ on the same ray and does not assume any convexity.

The second delicate step is the characterization of the kernel as an intersection of half-planes. If $X$ lies outside the half-plane corresponding to a side $e$, then every segment from $X$ to an interior point of $e$ approaches that side from the exterior side of its supporting line. Such a segment cannot remain inside the polygon. This excludes $X$ from the kernel.

The third delicate step is the converse. A careless proof might assert that if both endpoints of a segment belong to all half-planes, then the segment automatically lies in the polygon. What is actually needed is that the segment lies in every half-plane $H_e$, because each $H_e$ is convex. Hence the whole segment is contained in $\bigcap_e H_e=L$, and therefore in the polygon. The convexity of each half-plane is the exact input that makes the argument valid.

Alternative Approaches

A different proof starts directly from visibility constraints. For each side $e$, consider the set of points from which every point of $e$ is visible. This set is exactly the half-plane $H_e$ containing the interior adjacent to $e$. A point sees the entire shoreline precisely when it belongs to all these sets simultaneously. The visibility region is therefore $\bigcap_e H_e$.

After this identification, convexity and the bound $m\le n$ follow immediately from elementary properties of intersections of half-planes. This approach avoids introducing the kernel explicitly, but it hides the geometric reason why seeing only the boundary is equivalent to seeing the whole polygon. The kernel argument makes that equivalence transparent and isolates the essential geometric fact.