Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We are given a set of (marked) points in a 2D coordinate system and function $f(x,y)$ which counts number of points marked in the rectangle $(0 , 0), (x , y)$ - where $(0 , 0)$ if down-left corner, $(x , y)$ is up-right corner and sides are parallel to $x$-axis and $y$-axis.

How could we determine the number of points marked inside or on the boundary of the triangle with coordinates $(x_1,y_1),(x_2,y_2)$ and $(x_3,y_3)$?

For example if the given set of points is $\{(1,5),(1,3),(3,6),(4,4),(2,6)\}$, then there are exactly $3$ marked point inside or boundary of the triangle $\{(4,5),(1,5),(1,8)\}$, exactly $3$ marked point inside or boundary of the triangle $\{(5,5),(1,5),(1,9)\}$ and $0$ marked point inside or boundary of the triangle $\{(2,1),(1,1),(1,2)\}$.

I am aware of the approaches like these. However, I am more interested in solving this with the help of the function $f(x,y)$.

PS: For this particular problem we can also assume that everything is from the set of natural numbers.

share|improve this question
    
Does $f$ include marked points on the boundary of the rectangle? –  Blue Feb 9 '13 at 6:28
    
@Blue:Yes.$\space$ –  Ryan Earlington Feb 9 '13 at 6:44
    
Taking $x$ and $y$ positive ... Define $g(x,y) := f(x,y) - f(x-1,y) - f(x,y-1) + f(x-1,y-1)$. Then $g(x,y) = 1$ when point $(x,y)$ itself is marked, and $g(x,y) = 0$ otherwise. Then sum $g$ over the points in the triangle ... which is probably easier said (or typed) than done. Hmmm ... –  Blue Feb 9 '13 at 6:59
    
This is only solvable due to the assumption that "everything is from the set of natural numbers" (I suppose this applies to coordinates; distances and areas are of course are likely to not be natural numbers). Then your "triangles" are just finite sets of points in a grid, you can cover them by rectangles and add up. With non-integral coordinates you can never cover a triangle with a finite set of rectangles without also covering points outside the triangle. –  Marc van Leeuwen Aug 16 '13 at 10:07

1 Answer 1

Assuming a finite set of points, and allowing their coordinates to range over $\mathbb R$, let $g(x_1,y_1,x_2,y_2)=f(x_2,y_2)-f(x_2,y_1)-f(x_1,y_2)+f(x_1,y_1)$. This function counts the number of points in the rectangle $x_1<x\le x_2$, $y_1<y\le y_2$.

First draw a box around the triangle. The number of points in the triangle is equal to the number of points in the rectangle minus the number of points in each of the grey areas. Note that we can always subdivide the grey areas into rectangles (D) and right angled triangles (A,B,C)

Subdividing triangles $$ $$ Finding the number of points in a rectangle is easy, just use our function $g$. To find the number of points in a right angled triangle we will have to keep subdividing. Looking at the bottom picture and searching for the number of points in the white triangle we cut it into four pieces. Points in E are not in the right angled triangle, and points in H are. We are then left with two more smaller right angled triangles F & G which we can divide again repeatedly. Assuming there are only finitely many points we will hopefully reach a situation where both F & G are empty and thus no further subdivisions are necessary.

However, points lying near the diagonal line might require a very large number of iterations before discovering which side they are on, and those lying exactly on the boundary may cause us to never terminate the subdivision. I'm not sure of any way to avoid this problem if the only information on point locations is using the function $f$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.