Re: smallest slab enclosing n points
From: Dave Eberly (dNOSPAMeberly_at_usemydomain.com)
Date: 03/15/05
- Previous message: Craig Feinstein: "Re: Factoring integers on a classical computer"
- In reply to: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Next in thread: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Reply: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 15 Mar 2005 04:16:34 +0000 (UTC) To: geometry-research@moderators.isc.org
"Kent Paul Dolan" <xanthian@well.com> wrote in message
news:1110838099.871686.107710@l41g2000cwc.googlegroups.com...
>> By the way, Kent Paul Dolan's suggestion was first
>> to compute the convex hull of the data points.
>> That is Omega(pow(n,floor(d/2))), which can be
>> quite expensive for large d.
>
> I don't think so; here:
<snip>
My mistake in copying the information from O'Rourke's
book on computational geometry. The bound I mentioned
is for number of facets. However, to be pedantic, if you
have to process the facets (such as in printing them to a
file), the n*n bound you mention does not work. In a
practical application you *are* likely to do something
with the facets. But as you mention next, the actual data
sets might have some structure that lead to faster methods.
> http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf
>
> it says that the best known algorithms for Convex
> hull run in times dominated by n*n and significantly
> smaller (in one case, roughly n*h, where h is "hull
> vertex count") for non-pathological cases (see page
> 3), if I'm reading that correctly.
There are quite a few papers on the related problem of
Delaunay tetrahedralization that show the asymptotic
order is usually dependent on the structure of the data
sets. This is particularly important because it define
what "non-pathological" means.
>> Moreover, this relies on the OP finding a good
>> convex hull finder for large dimensions.
>
> Like this one?
>
> http://www.qhull.org/
Which is known to fail occasionally (as does just about everyone's
implementation if you find the right data set...)
> That's not a "convex hull" issue, that's a
> "cascading floating point computations" issue; in
> particular your eigenvalue/eigenvector calculations
> are going to suffer from precisely the same kind of
> robustness problems in large arrays for large "d".
Every floating-point algorithm in high dimensions suffers
robustness problems. What is your point? Mine was
that convex hull implementations do not always try to
algorithmically detect intrinsic dimension. In the
eigendecomposition of the covariance matrix, it does not
matter about the intrinsic dimension. Tridiagonalization
through Householder reduction followed by a QR (or QL)
algorithm is quite robust in large dimensions.
> And just what did you think your above proposal to
> "choose random directions" was going to involve?
> Point to hyperplane distance computations, of
> course, to see how thick the resulting slab would
> be (the easiest direction choice there is the normal
> to (any plane parallel to) the slab; the thickness
> then falls out as the signed difference of distances
> from the "n" points to such a slab. There's no free
> lunch here that I can see.
You project the points onto the line with the specified
projection and keep track of the min and max values.
The distance is max-min. Very trivial to implement.
Not so for point-to-simplex distance calculation.
> And by the way, there are "lots" of direction
> vectors required to sample at all adequately in a
> hypersphere with large "d". You might want to count
> what it takes to sample on average, say, every d-2
> sphere subtending at least "one degree" for d=7; the
> results are likely to gag you.
Yes, d-dimensional space for large d is quite large.
Is your convex hull approach any likely to be less
"gagging" than my approach?
> Or a bit of googling; I'm guessing Preparata nnd
> Shamos _Computational Geometry_, for one source,
> would contain such an algorithm.
I do not see a discussion of this in my copy. I am not
saying this is intractable, rather yet another piece of
the software the OP has to find or implement.
> If I were looking for a inexact one, I'd probably
> choose a genetic algorithm search over a Monte Carlo
> sampling approach, but that's just from lots of
> experience with GA success stories. However, the
> exact approach seems direct and well understood, so
> I'd try that first if an exact answer is more useful
> to the OP than an approximate one.
I never doubted the "direct and well understood" aspect
of your proposal to use convex hull. My point is that
in practice the OP might never locate good/robust
implementations of all the pieces the convex hull approach
requires.
Consider this yet another trade off in software engineering:
Exchange accuracy for development time.
-- Dave Eberly http://www.geometrictools.com
- Previous message: Craig Feinstein: "Re: Factoring integers on a classical computer"
- In reply to: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Next in thread: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Reply: Kent Paul Dolan: "Re: smallest slab enclosing n points"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
