| Main Page | Introduction | History | Preliminary | Algorithms | Applet | References |

____________________________________________________________________________________

Algorithms

Problem 1: let P={v0,..., vn-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 Tv0 be the triangulation of P given by joining v0 with all other vertices of P. Let Ti be the triangle with vertices{v0,vi,vi+1} and let Ri be its area, for i=1,...,n-2.

• Let A0 =0,A1 =0,A2 =R1,Ai =R1+...+Ri-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 P1 be the polygon including vertices v0,p,q, AT(pq) be the area of subpolygon with vertices v0,v3,p,q,v7,so the area of P1:

A(P1)=A4 + AT(pq) + A10 - A8

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={v0,..., vn-1} be a simple polygon, preprocess P so that for a query chord t of P we can quickly determine the area of Pt.

For any line segment t with the endpoints a and b, we denote A(t)=xayb - yaxb 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 e1 ,....en be the edges of P in counterclockwise:

Now use the idea of partial sums, for each edge ek, we store:

Suppose that chord t has its endpoints on the edges ej and ek,j<k-1.  Let A( t' ) be the sum of the area of:

A( t' )=A(vj-1a) + A(ab) + A(bvk)

So the area below the chord t  is:

A( Pt )=A( P )-Sk+Sj-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 Ai bounded by l and the lines 2i-1 and 2i (see Fig.2 )

we are given n lines, with line Li forming an angle bi>0 with the x axis, and intersecting it at x=ai . For a query line Q forming an angle a >0 with the x axis and intersecting it at x=t, let li be the signed length of the segment of Li delimited by Q and the x axis. The sign of li 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, ai =0, the bi are in increasing order, t=-1,  and for any query, a< bi for all i (and so t<0). then we get A(Q)

where u=cota, and bi = cotbi , note that A(Q) is a rational function in u and that the bi 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> cotb1 )

Now, construct a polygon P as follows: Starting with our n rays as above, pick three angles a0< a1< a2 <b1 , and let Q be the query line for angle aj (with t=1). Let pi,j be the intersection of line Li with Qj , i=1, ..., n. P (see Fig. 16)will have the sequence of vertices

Fig. 16

p1,0 ,  p2,0 ,  p2,1 ,  p3,1,  p3,0,..., p2i-1,0,  p2i,0,  p2i,1,  p2i+1,1,  p2i+1,0,..., pn,0,  pn,2,  p1,2,  p1,0

For any query line Q with angle a, a0< a< a1 , the area of upper subpolygon P1 cutting by Q is

A(P1)= A(P)- A(Q)+A(Q0

Theorem 3  Given a set of rays L={L1,..., Ln}, and k lines Q1,..., Qk each intersecting all n rays, we can compute for each area A(Q) in O((n+k)log2n)

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)log2n) time using FFT (Fast Fourier Transform)

__________________________________________________________________________________

| Main Page | Introduction | History | Preliminary | Algorithms | Applet | References |