This page reports two types of computational experiments to compare two algorithms, LP (naive) algorithm and LP+Clarkson algorithm, to remove redundancies in representations of convex polyhedra in general dimension. We will see how Clarkson's idea spectacularly improves the naive algorithm for highly redundant random inputs.
There are two representations of convex polyhedra, V-representation and H-representation.
As a V-representation, let Q be a given set of n points in R^d. To represent conv(Q), we only need its extreme points, thus to remove non-essential (redundant) points is a fundamental problem in computational geometry and mathematics in general.
A straight forward algorithm is to solve n LPs (linear programs) of O(n) constraints in d variables. Clarkson found a much more efficient algorithm that solves the same problem by solving n LPs of O(s) constraints in d variables. Here s is the number of essential (extreme) points. Thus the size of LPs to be solved is much smaller if s << n. We call s/n the essential ratio, and 100 x s/n the essential percentage.
If you are not familiar with Clarkson's algorithm, the textbook on Polyhedral Computation (Chapter 7) gives a detailed account of the algorithm and its complexity.
What would be a practical impact of Clarkson's algorithm? To answer this question, we have performed a preliminary experiment.
Here are important remarks on the experiment.
Float | Exact (Rational) | |||||
---|---|---|---|---|---|---|
LP algorithm | LP+Clarkson | Speedup | LP algorithm | LP+Clarkson | Speedup | |
UCUBE | ||||||
ucube10k_4d (4%ess) | 22s | 2s | 11 | 224s | 25s | 9 |
ucube20k_4d (2%ess) | 83s | 3s | 28 | 842s | 50s | 17 | ucube40k_4d (1%ess) | 331s | 6s | 55 | 3124s | 118s | 26 |
ucube10k_5d (9%ess) | 32s | 4s | 8 | 295s | 70s | 4 |
ucube20k_5d (6%ess) | 118s | 11s | 11 | 1068s | 169s | 6 | ucube40k_5d (3%ess) | 465s | 24s | 19 | 3902s | 403s | 10 |
ucube10k_6d (18%ess) | 43s | 11s | 4 | 399s | 151s | 3 |
ucube20k_6d (13%ess) | 175s | 29s | 6 | 1463s | 401s | 4 | ucube40k_6d (9%ess) | 699s | 84s | 8 | 5854s | 1060s | 6 |
DOUBLE UCUBE | ||||||
ducube10k_4d (0.6%ess) | 17s | 0s | * | 227s | 5s | 45 |
ducube20k_4d (0.4%ess) | 67s | 1s | 67 | 981s | 15s | 65 |
ducube40k_4d (0.3%ess) | 327s | 3s | 109 | 3794s | 46s | 82 |
ducube10k_5d (0.8%ess) | 19s | 0s | * | 275s | 9s | 31 |
ducube20k_5d (0.6%ess) | 94s | 2s | 47 | 1071s | 25s | 43 | ducube40k_5d (0.4%ess) | 409s | 4s | 102 | 4553s | 65s | 70 |
ducube10k_6d (1.3%ess) | 23s | 1s | 23 | 312s | 12s | 26 |
ducube20k_6d (0.8%ess) | 103s | 2s | 52 | 1302s | 34s | 38 | ducube40k_6d (0.7%ess) | 449s | 7s | 64 | 4969s | 106s | 47 |
For higher dimensional (27d and 35d) experiment, go to Ctype Experiment.