# Visibility and Kernel of Polygon

I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and fell free to share with us your opinion.

Basic theory for problem 1:

A $q$ is a visible point in polygon $P$, if for every point $p \in P$, the segment $pq$ is entirely in $P$.

Problem 1:

Prove that $q$ is a visible point in polygon $P$, if every vertex $v_{i}$ of polygon $P$ can see $q$.

Proof of problem 1:

In convex polygon every point is defined as visible point, by definition of convex polygon, every segment between points of convex polygon is contained inside convex polygon.

In arbitrary polygon not every point is visible point. If we can separate nonconvex polygon to minimal number of convex polygons all visible point are contained on the line common to all convex polygons (if it exists). So obviously if all visible points placed on the common line they are visible from all vertex of initial nonconvex polygon.

The problem of point visibility related to the art gallery problem,on this case only one guard will be sufficient for the art gallery problem.

Basic theory for problem 2:

Kernel of polygon $P$ is a set of all visible point of $P$.

Problem 2:

Kernel of the polygon $P$ is the intersection of N half-planes.

Proof of problem 2:

To be more precise kernel is a intersection of left half-planes, with reference to a counterclockwise traversal of the boundary. Obviously, each half-plane is convex and the intersection of convex sets is again convex. Therefore by intersection of half-planes of the polygon we get a convex polygon which is contained in initial arbitrary polygon. By previous problem 1 we know that all points of convex polygon are visible points, therefore this convex polygon is a kernel.

I know the proofs are not enough strict and rigorous, fell free to modify them or write new one.

Thank you very much.

-

Problem 1: If $q$ sees every vertex of a polygon $P$ then $q$ sees all of $P$. (This is for simple polygons, it is not true in polygons with holes)
Can you prove that if $q$ sees every vertex of $P$ then $q$ sees all points on the boundary of $P$? Then, using the fact that $q$ sees all edges of $P$, take any point $p$ in $P$. Take the ray $\overrightarrow{qp}$ and note it's intersections with the boundary of $P$, say $r$. There will be exactly 1 such intersection, as otherwise $q$ wouldn't see the farther points. $q$ sees $r$, so the line segment $qr$ is in $P$. Since the segment $qp$ is a subset of $qr$ it must also lie in $P$. Therefore, $q$ sees $p$.
Problem 2: The kernel of a polygon $P$ is the intersection of $N$ half-planes.
From Problem 1, a point $q$ sees all of $P$ if and only if it sees every vertex of $P$. To find the kernel, we want to find all points that see all vertices of $P$. To see each vertex, the point $q$ must see each edge completely. To see each edge completely, $q$ must lie on the inside of the half-plane defined by the edge. Therefore, a point $q$ sees all of $P$ if and only if it is contained in the half-plane defined by each of the $N$ edges. That is, a point $q$ is in the kernel if and only if it is in the intersection of $N$ half-planes.
Not quite. Take an edge $e = (v_1,v_2)$ of the polygon. Since $q$ sees both $v_1$ and $v_2$, look at the triangle, $qv_1v_2$. The line segment from $q$ to any point on $e$ lies entirely in the triangle. No edge of $P$ can cross the triangle boundary, and because $P$ is simple there are no holes in the triangle. That means that the entire triangle is contained in $P$, and so any line segment from $q$ to $e$ lies in $P$, and $q$ sees $e$. – Michael Biro May 8 '12 at 18:53