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.

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its set of vertices.

Is there a similar method to efficiently compute the sum

$$\sum_{(x,y)\in \mathcal{P}} x$$

where $\mathcal{P}$ is some lattice polygon? In other words, are there any methods to compute the "center-of-mass" of the set of lattice points belonging to the interior/boundary of a given lattice polygon?

(By efficiently, I mean something on the order of the number of vertices of the polygon. Also, by triangulation it's clear that it suffices to answer this question for lattice triangles)

EDIT: In case it was unclear, I am not trying to find the actual center of mass of the triangle - I want to find the center of mass of the set of lattice points inside the triangle (hence the above sum).

EDIT 2: After working on this problem a bit more, I think I've arrived at a fairly simple method which seems to work and avoids the messy machinery of 3D-Ehrhart polynomials.

The idea is (just as in Pick's theorem), since we can inscribe any triangle inside a rectangle, it suffices to compute the sum for rectangles and right triangles. Computing the sum for rectangles is easy; it's just something like $(y_2-y_1)(x_1+(x_1+1)+...+x_2)$.

Because of symmetry, it's almost as simple for right triangles. Namely, the sum of x-coordinates in/on the boundary of any right triangle is just equal to ((sum of x-coordinates in the corresponding rectangle) + (sum of x-coordinates along the diagonal))/2.

Hopefully this helps anyone who later has the same problem.

share|improve this question
5  
The center of mass of a triangle is just $\frac{1}{3}$ of the sum of its three corner coordinates. So that gives a linear-time algorithm, by multiplying the cg of each triangle by its area, summing, and dividing by the total area. –  Joseph O'Rourke Jul 31 '11 at 23:25
2  
@Joseph: that comment should be an answer. Incidentally, you wouldn't use Pick's theorem for the area of a triangle (method 7 of this list of area calculations if you know the vertices of the triangle, but method 6. –  Henry Jul 31 '11 at 23:41
1  
But it does not seem to be the center of mass of the triangle or polygon that is being sought. –  André Nicolas Aug 1 '11 at 0:01
2  
To be clear, I don't want the area of the triangle (or the actual center of mass, which is why I put it in quotes). I want to calculate the center of mass of the set of lattice points inside the triangle. –  jschn Aug 1 '11 at 3:00
1  
Edges of the triangle will "weigh" into the final product in proportion to the gcd of the x and y components of the associated displacement vector: I predict this could cause significant potential asymmetry and deviation from the true center of mass, and possibly give a number-theoretic flavor to the problem. –  anon Aug 1 '11 at 3:28
show 2 more comments

1 Answer

up vote 2 down vote accepted

It depends on what you mean by efficient. Computing $$\sum_{(x,y)\in P}x$$ is equivalent to computing the number of lattice points in a 3d polyhedron (basically $P$ with a slanted roof.) This is a job for Ehrhart polynomials. If you decompose $P$ into triangles you can decompose the triangle's corresponding polyhedron into a triangular prism (for which computing the lattice points therein is just an application of Picks Theorem) and two tetrahedra, which are straightforward to deal with, but fiddly (see the mathworld page referenced above.) All of this is explained clearly in great detail in Computing the Continuous Discretely.

share|improve this answer
    
Thanks for the Ehrhart polynomial reduction; I was aware of the theory of Ehrhart polynomials, but didn't immediately see how to reduce it to one. –  jschn Aug 1 '11 at 17:40
add comment

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.