Re: A partitioning problem
- From: israel@xxxxxxxxxxx (Robert Israel)
- Date: 12 Aug 2006 01:01:39 GMT
In article <44dd0fdb$1@xxxxxxxxxxxxxxx>,
Hans <luyang.han@xxxxxxxxxxxxxxxxxx> wrote:
Any one has some idea how to solve such a problem, with a proper algorithm?
Assume a 2D rectangular area, within which there are N different points. The
coordinate of each point is known. Now this area should be divided into some
polygons which meet:
1. The total number of polygons is the same as points, and within each
polygon there is just one point.
2. The point is at the mass center of the polygon.
By "mass center" I assume you mean centroid.
3. As mentioned above, the polygons should not overlap with each other, but
their union is the original rectangle.
Can't be done in general. Note that the centroid of the union of several
disjoint regions is the average, weighted by area, of the centroids of the
regions. The weighted average is in the convex hull of the points being
averaged. So if the centroid of the rectangle is not in the convex hull
of the N given points, there is no solution.
Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.
- References:
- A partitioning problem
- From: Hans
- A partitioning problem
- Prev by Date: Re: An uncountable countable set
- Next by Date: Re: An uncountable countable set
- Previous by thread: A partitioning problem
- Next by thread: In search of a simple proof
- Index(es):
Relevant Pages
|
