Grids

Polygon triangulation is, as its name indicates, is the processes of breaking up a polygon into triangles. Formally, A triangulation is a decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals. The set of non-intersecting diagonals should be maximal to insure that no triangle has a polygon vertex in the interior of its edges. example

The triangulation of polygons is a basic building block of many graphical application. High speed graphics rendering typically rely on subdividing curved surfaces into triangles for efficient handling by the hardware. Triangulating a polygon is a fundamental problem in computational geometry.

Every simple polygon admits a triangulation, and any triangulation of a simple polygon with $n$ vertices consists of $n-2$ triangles.

gons

Let $u$ and $w$ be the two neighboring vertices of $v$ on the boundary of $P$. If the open segment $\overline{uw}$ lies in the interior of $P$, we have found a diagonal. Otherwise, there are one or more of those vertices, let $v \prime$ be the one farthest from $\overline{uw}$. The segment connecting $v\prime$ to $v$ cannot intersect an edge of $P$, because such an edge would have an endpoint inside the triangle that is farther from $\overline{uw}$, contradicting the definition of $v\prime$. Hence $\overline{vv\prime}$ is a diagonal. Once we have established that a diagonal exists then we can say that any diagonal can cut $P$ into two simple polygons say $P_a$ and $P_b$. Let $v_1$ be the number of certices of $P_a$ and $v_2$ be the number of vertices of $P_b$. $V_1$ and $V_2$ must be smaller than $n$, so by induction $P_a$ and $P_b$ can also be triangulated. This means $P$ can also be triangulated.

Suppose you have an art gallery that contains works of famous painters that are not popular among art lovers but also among criminals.

image

Art galleries therefore have to carefully guard their pieces. During the day security personnel can keep a lookout, but a t night this has to be done via security cameras. You would like to place enough of these cameras such that at any one time every part of the whole gallery is overseen. To make things simple, let us assume that the floor plan of the gallery is a simple polygon. Let us also assume that the security cameras cannot move and they are to e placed in the corners , or vertices of the polygon.

Art Gallery Theorem: For a simple polygon with $n$ vertices, $\lfloor \frac{n}{3} \rfloor$ cameras are always sufficient to have every point in the polygon visible to at least one of the cameras.

Let us start with a simple case, a convex polygon with $n=3$ sides( a triangle). A camera placed at the vertex of the triangle can clearly oversee the whole triangle. This is because any line connecting any two points in the triangle is entirely contained within the triangle.

Now consider the general polygon. If we are able to break it up into triangles, then a guard placed at the vertex of a triangle can oversee each individual triangle and thus the whole polygon will be safely guarded.

The polygon described above can also be thought of as a graph, with each of the vertices representing a node.

graph

The problem now reduces to the graph coloring problem. If we want to color the vertices using three different colors so that every triangle has no two vertices with the same color. Let red,green and blue be the colors used. Each triangle must have each of the three colors at its tree corners. Thus each triangle has a red node at one corner. Thus, the entire polygon is covered if guards are placed at red nodes. Similarly the entire polygon is covered if guards are placed at green nodes or blue nodes.

The final step involves applying the pigeon hole principle. If $n$ objects are placed into $k$ pigeon holes, then at least one hole must contain no more than $\frac{n}{k}$ objects. For if each one of the $k$ holes contained more than $\frac{n}{k}$ holes, the total number of objects would exceed $n$. In our case , the $n$ objects are the $n$ nodes of the triangulation graph, and the $k$ holes of the three colors. The principle says that one color must be used no more than $\frac{n}{3}$ times. Since $n$ is an integer, we can conclude that one color is to be used no more than $\lfloor \frac{n}{3} \rfloor$ times. Thus proving the theorem.

If we want to find a triangulation of a convex polygon in linear time, we can just pick an arbitrary vertex $v$ and construct chords from $v$ to each other vertex in the polygon. Because of its convexity, we can be sure that none of the boundary edges of the polygon will be intersected by these chords. We can also be sure that all of them lie within the polygon. The simplest algorithm for constructing general polygon triangulation tries each of the $O(n^2)$ possible chords and inserts them if they do not intersect a boundary edge or previously inserted chord.

Most of the geometric problems we have discussed, especially polygons can be naturally decomposed into individual cells if some sort of grid is defined. Doing this is useful to be able to solve certain computational problems on these cells. Triangulation will not be difficult. We can insert either one of the two diagonals in a square or all three diagonals radiating from any point in a regular hexagon triangulates it. This works only because these figures are convex; notches and bumps makes this problem harder.

Range Queries

Given a set of points in the plane, it is natural to ask which of those points falls withing some specified area. "List all cities within 50 miles of Amsterdam" is a question of this type which could be reasonably asked if a set of points corresponding to cities were available. In general, we assume that we have a set of records with certain attributes that take on values from some ordered set. Finding all records in a database that satisfy specified range restrictions on problem in practical application.

Let us for the sake of simplicity however consider queries of the form on a $n \times m$ rectilinear grid L "What is the sum of the values in a given sub-rectangle of the matrix"?

Any axis oriented rectangle can be specified by two points: the upper-left-hand-corner$(x_l,y_l)$ and the lower right corner $(x_r,y_r)$. The simplest algorithm is to run a nested loop adding up values a[i][j] for $x_l \leq i \leq x_r$ and $y_r \leq j \leq y_l$. This is however inefficient. Instead we can construct a second rectangular matrix such that element a1[x][y] represents the sum of all elements a[i][j] for $i \leq x$ and $j \leq y$. This dominance matrix makes it easy to find the sum of the elements in any rectangle because the sum of elements in such a box is:

1

S(xl,yl,xr,yr)=m1[xr][yl]-m1[xl-1][yl]-m1[xr][yr-1] + m1[xl-1][yr-1]

This yields an overall $O(mn)$ solution which is better.