New Page 2

____________________________________________________________________________________

Introduction

The measure of areas of sets is fundamental problem in mathematical and Computational Geometry. It is straightforward to see that calculating areas of polygons in the plane can be done in linear time, even for the following problems:

Suppose that we split a simple polygon P into two subpolygons P₁ and P₂ by cutting it along a line segment joining two mutually visible points s and t on its boundary, see Figure 1,

Fig. 1

can be solved optimally in linear time. But how quickly can we measure the areas of P₁ and P₂? So our solution here, is to present a simple and practical data structure for storing the partial sum's areas, so that after linear amount of preprocessing, P₁ can be gotten in constant time.

Given 2n rays from one point, for a query line l crossing all 2n rays, how 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 Figure.2 )? Here in this project the solution is given by using FFT (Fast Fourier Transform).

Fig.2

__________________________________________________________________________________