Created 2007-03-15 Modified 2007-03-15
Chelton Evans
Divide and Conquer
This is a variation of the Divide and Conquer algorithm as given in Computational Geometry in C [1]. I have generalized the algorithm by removing ordering on the x-axis as random half spaces are used instead. The algorithm itself generalizes to any dimension.
I am also considering the hull as a tessellation. Since the divide and conquer algorithm tessellates between two hulls the algorithm then becomes a tessellation algorithm.
Given w points in N dimensional space,
choose N points to create a half space and use
the half space to divide
the points in two.
Tessellate the convex hull of the two sets of points
by recursively calling this procedure.
Merge the two hulls from the two sets of points.
Randomly choose the points that create the half space.
For the algorithm in [1] instead of the half space test order the points on the x-axis, find the middle point and then split the points in two on the x-axis about the middle point. This is a half space perpendicular to the x axis.
Algorithm [1] does generalize to any dimension. Intersecting partitions al most intersect on the half space itself. This is a property of the algorithm in both cases.
A problem with [1] is that the partition using a random half space has a better complexity. Unless a special sorting algorithm is used, the sort is O(nlogn) complexity. But partitioning the points with a half space test (dot product) is O(n).
To further this point the complexity as given by the author[1] is not correct. If we assume that sorting is O(nlogn) then the actual complexity is given by the formula sum(i=0..logn, nlog(n/(2^i))). This is going to have a greater complexity than the claimed O(nlogn).
It is for this reason that I prefer the random half space partition as sorting is avoided.
You may notice that I ripped the guts out of the algorithm in [1] when it starts talking about specifics in 2D. For example the lower tangent algorithm is not mentioned.
This is because I consider merging to be a general algorithm, done in any dimension. Effectively given two convex tessellations of linked simplexes in N dimension which do not intersect each other (except perhaps on their boundaries), apply a merge algorithm to produce the merged tessellation.
I have not added the merge calculation complexity where a surface facet on either side must be found in each convex hull that sees the other convex object. This is another algorithm, but is O(logN) for a balanced convex hull meshes.
A more complicated merge strategy is the following algorithm. Each split records the half space that split it. The merge creates new simplexes. Save the surface simplexes that were newely formed - ie simplexes that in the merge have atleast one face with no neighbors.
In 2D this is 2 triangles. In 3D this is a ring of tetrahedrons. The pattern is N-2 where N is the spaces dimension.
Iterate over this ring or whatever to find a simplex that sees the original half space partition. So this for each side of the partition. However this can be improved. Instead when the merge simplex was created, have a pointer to a simplex that can see the half space partition. If the newely created merge simplex sees the partition have the pointer point to it. So when it comes time to merge two hulls it is simply a matter of accessing the pointers which is a constant time operation.
The diagram shows partitions that are at right angles and not points in the mesh. When points in the mesh are used then one of the convexes faces is automatically known so half the work is done there, then only the other convex object needs to find a face that sees the partition. The algorith gets further involved.
The cost of the merge is then based on how many facets the hulls have to be stitched up.
Finally at the end when the tessellation is complete the hull can be extracted from the mesh.