Re: straightness and flatness algorithm

jeff lyon wrote:

Roger, interesting points.

It is possible to have a set of three-dimensional points
for which the minimum distance between parallel planes
does not occur for a two-dimensional facet (three vertices)
in one plane and a single vertex on the other. Instead, the
minimum can in some cases occur with a pair of one-dimensional
edges contained in the two respective parallel planes.
An example of this is for the four vertices of the
classical regular tetrahedron solid where the minimum
distance occurs between opposite pairs of edges, not between
triangular faces and opposite vertices. You would therefore
need to add another point 4. to your outlined method to
provide for such cases.

That is absolutely true and I hadn't thought of that case. I guess
one way around this would be to include a second set of
calculations
to:

1. find the distances between all the lines that are part of the
convex hull,
2. check to see if the planes intersect the point cloud (if one
does,
it would not be a viable solution).
3. find the minimum distance of the viable sets of planes.

Doing this brute-force would be an O(n^2) problem, but it could
probably be optimized. Any ideas?

In the two-dimensional problem, there is a method called
the "rotating caliper algorithm" which uses a clever strategy
in seeking the min-max distance between an edge and a vertex
of a convex set of points. Instead of taking each edge and
finding the orthogonal distance of each vertex from this edge,
and then taking the min-max of these, which would be an order
n^2 algorithm, it proceeds around the convex polygon, one
successive edge after another, but at the same time
advancing independently around the opposite side from one
successive vertex to another. As these vertices advance they
must come to a single maximum for a given edge and then begin
decreasing. At that point the edge can then advance and the
opposite vertices commence advancing from where they left off,
again proceeding to a single maximum. In this way orthogonal
distances from no more than two times the total number of
vertices need be calculated, and the algorithm is therefore
only order n, not order n^2, an important consideration for
large numbers of points.

That's very cool. I bet this idea can be extended to R3. How about
the following basic hill-climbing algorithm? It takes advantage of
the convexity of the point set like you do for the rotating caliper
algorithm.
1. for a given facet on the convex hull, calculate the distance of
an
arbitrary vertex (not part of that facet) on the convex hull, say
p_j

2. calculate the distances to the vertices for the faces that also
share p_j and find the maximum distance in that set
3. if that new maximum distance is less than the distance to p_j,
you're done: p_j is the farthest virtex. otherwise, repeat step 2
for
the vertex with the new largest distance.

I guess in pathological cases this could still be an O(n^2)
problem,
for most cases I would think that its much faster. What do you
think?

Thanks,
Jeff
----------------------
Yes, that's a very good idea! There's hope for it. If the
"arbitrary" vertex in step 1. is already close to the maximum point,
you will certainly arrive at the maximum point quickly that way. The
problem as I see it is how to proceed through the facets of step 1 in
a methodical manner so as not to leave any out, and, except at the
beginning, always manage to begin with a vertex near the maximum.
If, in the facet of step 1, you move to one that is adjacent to it,
you could start with the vertex that had just been found to be a
maximum. But how do you go through all the facets in this manner so
that any two subsequent facets are next to each other on opposite
sides of an edge? I can think of schemes analogous to peeling off
strips of apple skin and baring the whole apple eventually with one
strip, where you always choose, say, the left of two edges of a
triangle to cross if their opposite sides are both as yet unoccupied.
But it seems to me I can also envision triangulation setups that I
think would defeat such a strategy and leave portions unused. The
trouble is, my octogenarian brain tends to blank out about the time I
try to envision this part of the problem.

Roger Stafford
.

Quantcast