| Main Page | Introduction | History | Preliminary | Algorithms | Applet | References |
____________________________________________________________________________________
Algorithms
Problem 1: let P={v_{0},..., v_{n-1}} be a convex polygon, preprocess P so that for a query line of P we can quickly determine the pieces of P.
Algorithm 1 Preprocessing convex polygons
Let T_{v0} be the triangulation of P given by joining v_{0} with all other vertices of P. Let T_{i} be the triangle with vertices{v_{0},v_{i},v_{i+1}} and let R_{i} be its area, for i=1,...,n-2.
Let A_{0 }=0,A_{1 }=0,A_{2 }=R_{1},A_{i }=R_{1}+...+R_{i-1},for i=3,...,n-1(see Fig.14).
Fig.14
The intersection points p and q of a line with the boundary of a convex polygon can be found in logarithmic time (see [PS85]). For example, in Fig.14 let P_{1} be the polygon including vertices v_{0},p,q, AT(pq) be the area of subpolygon with vertices v_{0},v_{3},p,q,v_{7},so the area of P_{1}:
A(P_{1})=A_{4} + AT(pq) + A_{10} - A_{8}
can be calculated in constant time, we have:
Theorem 1 : Given a convex polygon P with n vertices, after O(n) preprocessing time, the pieces of a convex polygon split by a line can be in O(logn) time
__________________________________________________________________________________
Problem 2: let P={v_{0},..., v_{n-1}} be a simple polygon, preprocess P so that for a query chord t of P we can quickly determine the area of P_{t}.
For any line segment t with the endpoints a and b, we denote A(t)=x_{a}y_{b} - y_{a}x_{b} and equals twice the area of the triangle whose vertices are the origin and the endpoints of t.
Let A(P) be the area of P and let e_{1} ,....e_{n} be the edges of P in counterclockwise:
Now use the idea of partial sums, for each edge e_{k,} we store:
Suppose that chord t has its endpoints on the edges e_{j} and e_{k,}j<k-1. Let A( t' ) be the sum of the area of:
A( t' )=A(v_{j-1}a) + A(ab) + A(bv_{k})
So the area below the chord t is:
A( P_{t })=A( P )-S_{k}+S_{j-1}+A( t' )
so we get:
Theorem 2: Given a simple polygon P with n vertices, there is a data structure that after O(n) preprocessing time can return the area of P below a query chord t in constant time
________________________________________________________________________________
Problem 3 ( Fan Problem): Given 2n rays from the origin construct a data structure which for a query line l crossing all 2n rays can quickly return the sum of the areas of the n triangles A_{i} bounded by l and the lines 2i-1 and 2i (see Fig.2 )
we are given n lines, with line L_{i} forming an angle b_{i}>0 with the x axis, and intersecting it at x=a_{i }. For a query line Q forming an angle a >0 with the x axis and intersecting it at x=t, let l_{i} be the signed length of the segment of L_{i} delimited by Q and the x axis. The sign of l_{i} will be positive if the intersection with Q is above the x axis, negative otherwise (see Fig 15).
Fig. 15
By using standard trigonometry, we obtain:
For simple discussion, we now apply several restrictions to this problem. for example, suppose n is even, a_{i} =0, the b_{i} are in increasing order, t=-1, and for any query, a<_{ }b_{i} for all i (and so t<0). then we get A(Q) _{ } _{ }
where u=cota, and b_{i} = cotb_{i} , note that A(Q) is a rational function in u and that the b_{i} can take arbitrary values.Then any data structure allowing queries for the fan problem will compute A(Q) accuratly for an infinite number of u's ( i.e. all u> cotb_{1} )
Now, construct a polygon P as follows: Starting with our n rays as above, pick three angles a_{0}< a_{1}< a_{2} <b_{1} , and let Q_{j } be the query line for angle a_{j} (with t=1). Let p_{i,j} be the intersection of line L_{i} with Q_{j} , i=1, ..., n. P (see Fig. 16)will have the sequence of vertices
Fig. 16
p_{1,0} , p_{2,0} , p_{2,1} , p_{3,1}, p_{3,0},..., p_{2i-1,0}, p_{2i,0}, p_{2i,1}, p_{2i+1,1}, p_{2i+1,0},..., p_{n,0}, p_{n,2}, p_{1,2}, p_{1,0}
For any query line Q with angle a, a_{0}< a< a_{1} , the area of upper subpolygon P_{1} cutting by Q is
A(P_{1})= A(P)- A(Q)+A(Q_{0})
Theorem 3 Given a set of rays L={L_{1},..., L_{n}}, and k lines Q_{1},..., Q_{k} each intersecting all n rays, we can compute for each area A(Q) in O((n+k)log^{2}n)
Proof: Because A(Q) is a polynomial, It is known that a polynomial of degree n can be evaluated for k values in O((n+k)log^{2}n) time using FFT (Fast Fourier Transform)
__________________________________________________________________________________
| Main Page | Introduction | History | Preliminary | Algorithms | Applet | References |