content_image/300723.jpg content_image/300721.jpg
C is exactly the number of ways to choose m − 4 and m − 5 points, respectively, from the points in the four outer areas. Again, the number of points in the four outer areas is calculable in O (1) using A . Since all cells are defined by two, three, or four points, there are no additional types of cells. 

<img src='content_image/300723.jpg'>

Let us denote the number of sample points in the four outer areas of a cell C by OUT . Further denote by C ( OUT ) the group of all cells which have exactly OUT points in the outer areas. For the sake of brevity, lets consider only cells of type 2. Similarly to equation (3.5) for the ADP statistic, the contribution to the score S DDP m × m of internal cells of type 2 can be written as 

<img src='content_image/300721.jpg'>

The algorithm proceeds as follows. First in a preprocessing phase we perform two computations: 1)go over all cells and calculate t$_{C}$ and OUT for each cell and update T ( OUT ) = T ( OUT ) + t$_{C}$ . This stage takes O ( N $^{4}$); 2) for all u,v ∈ { 0 ,...,N } we calculate and store all ( u v ) in O ( N $^{2}$) steps using Pascal’s triangle method. 

Now for each m , since n ( OUT,m ) = ( OUT m − 3 $^{)}$, given T ( OUT ), clearly equation (E.1) can be calculated in O ( N ) for a fixed m and in O ( N $^{2}$) for all m s. Therefore the total 

