Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you very much!!! Question 1: if q sees every vertex of P then q sees all points on the boundary of P? This is true, because every point on the boundary is the convex combination of endpoints? –  com May 8 '12 at 17:37
    
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
    
Hmmm, thanks for pointing this out! –  com May 8 '12 at 18:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.