REPLIES RECEIVED TO AVIS-FUKUDA RESPONSE TO CG TASK FORCE REPORT
-------------------------------------------------------------
Date: Thu, 09 May 1996 10:34:08 -0400
From: tim@cs.cosc.georgetown.edu (Tim Snyder)
Subject: Thanks
To: avis@mutt.CS.McGill.CA
Message-id: <9605091434.AA04995@vivid>
Content-transfer-encoding: 7BIT
Status: RO
David,
I concur with your comments; nice work!
Best,
Tim
Timothy Law Snyder
Dean of Science
Georgetown University
tim@manic.cosc.georgetown.edu
Date: Thu, 9 May 96 12:54 EDT
To: avis@mutt.CS.McGill.CA
Subject: Convex hulls
Status: RO
Dear David,
I wish to take exception with your statement:
"We can find no evidence of the methods proposed in CG literature
actually being used, in spite of the fact they have been widely
known for many years."
The qhull program for finding convex hulls (coded at the Geometry
Center) is based on the Clarkson-Shor randomized incremental
algorithm, and your paper indicates that it does not have bad
performance. If you use the argument that it is based on ideas
that appeared in the literature before, I would argue that nobody
paid any attention to these ideas before a theoretical proof of
efficiency.
That having been said, I totally agree with your point that
computational geometry does not pay enough attention to practice.
Peter Shor
From: Jeff Erickson
To: avis@mutt.CS.McGill.CA (Prof. David AVIS)
Date: Thu, 9 May 1996 12:42:17 -0700 (PDT)
Professor Avis --
With your permission, I would like to include your well-written
response to the recent CG taskforce report in my computational
geometry WWW pages.
Before including it, I would reformat your response as an HTML
document and add appropriate links (to the taskforce report, to your
paper with Fukuda and Seidel, etc.)
(in: http://http.cs.berkeley.edu/~jeffe/files/avis.html)
Of course, I would attribute copyrights to you and Professor Fukuda.
Please let me know if this is okay.
All the best!
-- Jeff
From: joe malkevitch
To: "Prof. David AVIS"
Dear David,
I enjoyed your comments on the task force report. I also noted
in comments to Bernard that the report says almost nothing about educational
issues. Almost no high school teachers know that computational geometry
exists in the states, or what areas it might even potentially find
use. Similar problems exist at the college level. I recently went to a
geometry conference in Italy and from what I saw there, almost no
one attending was aware of computational geometry and the kinds of geometric
issues it raised.
Regards,
Joe
From: Nina Amenta
To: compgeom-discuss@research.att.com
Subject: Impact
I'm writing in reply to David Avis and Komei Fukuda's message a couple
of days ago. It's nice to see some discussion on this mailing list!
Especially important discussion!
They raise an issue that was not addressed by the CG Impact Task Force
Report: even basic problems like linear programming and convex hull
cannot be considered solved outside of the most restrictive model of
worst-case complexity. This is a good criticism; when you consider
constants and output-sensitivity it is clear that there is a lot of
theoretical work still to be done in the core areas.
But I think this is an effect of the dissociation of CG from practice,
rather than the cause of the dissociation, as they argue. If the field
becomes more concerned with providing convex hull programs, rather
than convex hull algorithms, a more realistic model of complexity will
take over the culture. If we push practice, theory will follow. So I
think the emphasis of the Report was right.
Also I don't think work on LP and convex hull algorithms has been
quite as skewed as they portray it to make their (generally valid)
point. In LP, Clarkson, Seidel and Kalai/Matousek-Sharir-Welzl
addressed the issues of the size of the constant, simplicity, and
subexponential simplex algorithms. And Seidel and Avis both worked on
output sensitive convex hull algorithms. The problem as I see it is
that (except for Avis's qrs and Hohmeyer's LP program) none of this
has lead to published software, so the *impact* has been minimal.
Finally, Avis and Fukuda write "We can find no evidence of the methods
proposed in CG literature actually being used, in spite of the fact
they have been widely known for many years." Two years ago we clocked
890 copies of qhull downloaded from The Geometry Center. I'd expect
it's twice that now. Anyone else have any data points? I'd be really
curious.
I hope we all get a chance to talk about these issues ``live'' at SCG
and WACG (including the technical stuff about Motzkin's algorithm).
See you soon, Nina
PS Avis,Bremner,Seidel, ftp://mutt.cs.mcgill.ca/pub/doc/hgch.ps.gz
is indeed pretty interesting!
Date: Tue, 14 May 1996 15:14:46 +0200
From: seidel@cs.uni-sb.de (Raimund Seidel)
To: avis@mutt.CS.McGill.CA
Subject: Impact
Dear David,
I read with some amazement your comments on the Impact Task Force Report.
At this point I am uncertain, whether you just want to be polemic,
or whether you simply don't know (or choose to ignore) some facts.
First about Linear Programming:
> The result cited is that, in any fixed dimension, an LP may be solved in
> linear time, which is clearly "optimal" and a big improvement on the
> simplex method which runs in (roughly) O(n^{d/2}) time. (Under most
> models the simplex method is an exponential time algorithm, but under
> the CG model it is polynomial in each fixed dimension!) The result cited
> dates to 1983 yet seems to have no impact on either the theory or
> practice of linear programming, which is busy refining interior point
> methods and trying to find a truly polynomial simplex-like algorithm.
> The reason is well known: a huge constant depending on the dimension is
> hidden.
No, there is more than just Megiddo's result.
There is Clarkson's sampling based result, which roughly says, that
the only difficult types of linear programs are those where the
number of variables and number of constraints are not too far apart
(He gets something like m<=9d^2). If you have a greater imbalance,
then it can be reduced at linear expected cost, essentially.
This fact that LPs with reasonably balanced numbers of variables
and constraints are the hard ones was of course empirically known
in the optimization community. Usually it is described as that
empirically the running time of the simplex algorithm increases
linearly with the number of variables (or they say, the number
of pivots appears to be fairly insensitive to the number of variables).
However, as far as I can tell, there has been no satisfactory
theoretical explanation for this fact, save for the one that is
implicitly provided by Clarkson.
You say "the theory of linear programming has been busy trying to
find truly polynomial simplex-like algorithms".
Now tell me, which provable results have been achieved in this direction
except for the ones that make some input distribution assumption?
As far as I can tell (but I am eager to learn more) the best results
are the randomized algorithms by Kalai, and by Matousek-Sharir-Welzl,
which, as it turns out, are essentially the same, except one is formulated
as primal, the other one as dual. Yes, MSW is, when specialized to
linear programming, nothing but a dual simplex algorithm. If you read
their paper, then you will notice that the main thrust is not to
show that the running time depends linearly on the number of constraints
(this is taken care of by Clarkson's result). The main thrust
is the analysis for the case of very few constraints, and the main
result is that the dependence on the dimension is only \exp{O(\sqrt{d})},
i.e. subexponential, algthough not yet polynomial. (There are explicit
constants in the paper).
In addition to giving a pivoting strategy with the best known
(probabilistically) guaranteed performance, the paper also provides
an abstract framework for optimization problems to which
oriented matroids, an apparent favorite among optimization theorists,
in terms of algorithmic applicability and significance pale in comparison.
Now to the convex hull problem:
> CH3 is the convex hull problem that arises frequently in practice,...
First of all, I venture that except for problems arising out of combinatorics
CH4 (boundary triangulation) arises at least as often.
Let me reiterate that problem CH3 as such was never even considered
in computational problem, and hence also not solved. (There may be
good complexity theoretic reasons for that.)
> In summary, even though the convex hull problem is declared "solved" in
> the CG community, the methods proposed do not solve even quite small
> practical problems that can be solved (but not well) by other methods. A
> realistic model of computing reveals this instantly.
I made a little experiment: Compute the convex hull of n points of the
form (x^2+y^2+z^2,x,y,z) with x,y,z chosen uniformly at random from [0..1023].
I used cdd-056 with floating point (since I knew that rational would be
much much slower), and I used the program chD by Ioannis Emiris, which
is a CG type insertion algorithm ("worst case optimal for even d",
which you love so much), which has a careful rational implementation
and uses perturbations. Both programs used lexmin insertion order.
Here are some running times:
n chD cdd
(hh:mm:ss) sec sec (hh:mm:ss)
1000 (00:04:24) 264 710 (00:11:50)
2000 (00:09:51) 591 6748 (01:52:28)
3000 (00:15:49) 949 21997 (06:06:37)
chD for d=4 has a provable worst case running time of O(n^2).
On the random examples it has an apparent slightly superlinear
running time.
cdd does not state any worst case running time (for d=4 it has
to be at least \Omega(n^5)). The list is a bit short to extrapolate
reliably, but the actual running time on the examples appears to
be cubic, which would be consistent with an informal analysis.
But this is really irrelevant, since chD is so much faster on those
examples.
I tried a similar experiment for d=8.
n chD cdd
(hh:mm:ss) sec sec (hh:mm:ss)
100 (03:21:47) 12107 29018 (08:03:38)
200 (17:29:20) 62960 not solved because of
apparent floating point problems
Don't tell me that cdd is the method of choice for such examples.
And don't tell me that such examples are irrelevant, or don't
occur in practice. Herbert's 3-dimensional alpha-shape program
which soon will be on the market commercially) routinely has to
solve problems of this sort.
> Our recommendations are: (i) Replace the current theoretical model by
> one which is realistic, and reconsider all fundamental problems under
> this new model. As a minimum, complexity analysis under such a
> model should state explicitly dependence of constants on the
> dimension, and where output size varies greatly, be output
> sensitive. (ii) Rigorously enforce the scientific method: theory
> which does not stand up to empirical scrutiny should be revised or
> abandoned.
Re (i). Take a look at Garret Swart's paper and take
a look at my PhD thesis. The convex hull algorithms presented there
are analyzed explicitly with respect to input-size, output-size, and
the dimension. They may not solve the problem that you would like
to see solved (namely CH3), but what they do solve, they solve
exactly under the model that you propose as new.
Similarly, the LP algorithms proposed in CG are all analyzed explicitly
with respect to both number of constraints and the dimension.
As far as I am concerned, your recommendation (i) is completely void.
Re (ii). Thankfully there is no equivalent German expression to
"the scientific method". I think I understand what you mean
(although there seems to be some confusion between descriptive
and prescriptive theories). I believe still believe that it is
not so much that we have been doing "the wrong theory", but that
the problem is that we have failed to reasonably make the theory
available to practice.
All the best!
Raimund
From: "Ken Clarkson"
Date: Tue, 14 May 1996 10:10:30 +0400
To: compgeom-discuss@research.att.com
Subject: Re: Impact
Status: R
I'd like to follow up on the discussion begun by Komei Fukuda and David
Avis. Like Nina Amenta, I'm pleased (hey, thrilled) to see
compgeom-discuss actually used to discuss something.
Among other points, Avis and Fukuda make the following observations:
(1) The asymptotic worst-case complexity of an algorithm is not always
a good indicator of its performance in practice.
(2) Geometric algorithms that are good in low dimension are not
necessarily good in high dimension.
These issues are very important, and I'm glad that Avis and Fukuda have
brought them up. I agree with their general outlook, but I disagree with
some details in their discussion. In general, I'd like to follow up
and expand on Nina's comments.
Convex hulls
Avis and Fukuda suggest that these points are particularly relevant in
the areas of linear programming and convex hulls. For convex hulls,
they support point (2) with the beautiful and important results of
(Avis,Bremner,Seidel, ftp://mutt.cs.mcgill.ca/pub/doc/hgch.ps.gz),
where various problem instances show that some convex hull algorithms
can have a running time greatly out of proportion to their output size,
for some classes of convex hull problems in dimension as low as 8.
While a few of the problem instances arose in practice,
the bulk of the results in the paper, both theoretical and empirical,
seem to be worst-case constructions. Thus many results in the paper are
contrary in spirit to point (1).
I'm skeptical that convex hull problems in dimension higher than 8 have
great significance in practice, compared to those in lower dimension;
this may be, of course, because effective algorithms weren't available
for the higher dimensional problems. However, most of those who have
expressed interest in, or used, my hull code have wanted to compute
Delaunay triangulations in two or three dimensions. I think this is
true also for the very much larger group of users of qhull. The
question here is: in what dimensional regime do "important" convex hull
problems lie? It would be helpful to have a collection of convex hull
problem instances, arising in practice, with which to compare
algorithms and to help answer these questions.
Avis and Fukuda contrast asymptotic worst-case complexity with
output-sensitive bounds, and note that the worst-case optimal
complexity of O(n^\floor{d/2}) held by some convex hull algorithms is
so much higher than the output size for practical problems as to be
irrelevant. I think it's worth mentioning here a long-known bound for
some randomized algorithms that is not output-sensitive, but may have
some relation to practice. Some randomized convex hull algorithms take
time on the order of
n sum_{1\leq r\leq n} d^2 f_r/r^2,
where f_r is the expected complexity of the convex hull of a random
subset of size r. (More precisely, f_r bounds the complexity of a
triangulation of the convex hull, cf. Avis and Fukuda's problem CH4.)
I believe that for many convex hull problems arising
in practice, f_r is O(r) or even o(r), giving an expected running time
of O(n log n). While it is quite easy to concoct problem instances
where f_r is Omega(r) but the output size is O(1), I think
that nature is not usually as perverse as that. Again, however,
I really don't know.
I agree that in very high dimensions, such randomized algorithms based
on beneath/beyond methods may not competitive with output-sensitive
algorithms. I would also not be surprised to find that parts of these
randomized algorithms could be replaced by heuristic procedures such as
bucketing, and be somewhat faster. However, the relationship between
theory and practice for these algorithms is much less problematic than
Avis and Fukuda suggest. The algorithms are simple and are not
significantly slower than more complicated algorithms that use
heuristics, even for problem instances for which the heuristics work
well.
Finally, I see no reason to consider different algorithms, for different
dimensional regimes, to be in competition.
Linear programming
Avis and Fukuda imply that work in computational geometry on linear
programming has failed to consider dependence on the dimension. As
Amenta observed, this is not the case. Indeed, I know of no such work
that has *not* included explicit expressions for dimensional
dependence. More than one person has suggested that a bound of mine
for linear programming,
\[O(n d^2)+(\log n)O(d)^{d/2+O(1)}+O(d^4\sqrt{n}\log n),\]
gives just a little bit too much detail on the dependence on the
dimension d. Note that the dependence on d here is not huge, and the
exponential dependence on d follows from a worst-case bound for the
simplex method; in practice, this bound can be replaced by a low-degree
polynomial.
Avis and Fukuda suggest that in contrast to work in computational
geometry, most researchers in linear programming are more interested in
greater understanding of the interior-point and simplex methods. It's
worth mentioning that at least three algorithms from CG can be viewed
as versions of the simplex algorithm with particular pivoting rules: a
recursive one of mine, and the algorithms of Kalai, and of Matousek,
Sharir, and Welzl; the latter amazing algorithms are the only provably
subexponential simplex algorithms known. Note that this work comes out
of the discrete and computational geometry communities, and is the only
progress toward a provably polynomial-time simplex algorithm.
I agree that low-dimensional linear programming is much less important
than the general case. However, the above algorithms, and many others
proposed in the CG literature, are applicable in the general case.
They have the added "insurance" that they are provably fast when n>>d.
It would be valuable to have a collection of problem instances for
low-dimensional linear programming that have arisen in practice; if
it's hard to come up with such a set, that would simply be evidence
against the practical importance of the problem. It would certainly
be of interest to determine the relative speed of CG algorithms
and simplex algorithms with various pivoting rules. My own limited
experience suggests that modest speedups are possible with
randomized algorithms; the programming overhead is quite small.
To conclude: I agree with points (1) and (2), but disagree with Avis
and Fukuda's statement that low-dimensional linear programming and
convex hulls "have not been solved in any realistic way" in the
computational geometry literature. I agree with their general points
about the importance of practical impact, the need to think carefully
about the models of computation we use in theory, and the importance of
working on algorithmic problems that actually come up in applications.
As I mentioned twice, a library of problem instances would useful. If
I feel foolish enough, I'll volunteer to maintain such a library; I'm
sure that several groups have some good instances already.
-Ken
From: "Prof. Azriel Rosenfeld"
Message-Id: <199605201849.OAA13829@parmenides.cfar.umd.edu>
To: compgeom-discuss@research.att.com
Subject: Comments on the Computer Vision chapter of the Task Force report
Cc: ar@cfar.umd.edu
Status: RO
Comments on Section 5 ("Computer Vision") of the CG Impact Task Force report
by Azriel Rosenfeld (ar@cfar.umd.edu)
Avis and Fukuda recently posted some critical comments on the report,
particularly as regards the unrealisticness of the theoretical model
used in CG. This impels me to make a few comments about the section
of the report that deals with applications in my field - computer vision.
I would encourage readers in related fields (image processing, GIS, etc.)
to consider doing likewise.
Computer vision (CV) does indeed make heavy use of pattern matching
techniques, both in model-based object recognition and in 3D reconstruction
(stereopsis, structure from motion). Obviously, CG has a lot to tell CV
about the matching of geometric (e.g., point) patterns; but the scope of
applicability of CG algorithms is limited by the fact that in CV, the
patterns are of bounded sizes - relatively sparse sets of "feature points"
detected in digital images of fixed dimensions, on the order of 1000 x 1000
pixels. (Image sensor resolution grows very slowly over the years; TV
stayed at 500 lines for a long time. Note that the human eye too has
limited spatial resolution, and the high-acuity part of the retina
produces images of essentially TV resolution.
This also limits the sizes of other representations of an image; the
boundary of a region (e.g., represented by a "chain code") typically
has (integer) length proportional to the region's diameter, which is
bounded by the image diameter. The numbers get bigger if we deal with
(discretely sampled, e.g. 30 frames/second) time-varying imagery, which
might provide challenges for dynamic CG; but here too, frame rates don't
grow arbitrarily, since the current rates are good enough to capture/mimic
"continuous" motion as far as humans are concerned.
Image representation is a topic common to image processing and computer
vision; the examples given in this subsection are illustrations of the
first, not of the second. Incidentally, digital images are obtained by
regular sampling at grid points, not by sampling at "arbitrary" points;
the "weighted Voronoi diagram" suggestion is an overkill for standard
bilinear interpolation of the grid. Perhaps the suggested solution is
worthy of the problem; "resolution enhancement" of a single digital image
is a thankless task - you can't create information that isn't there.
"Magnification" might have been a more realistic term.
Optimization methods of image segmentation are also quite extensively used
in CV; possibly the CG community has ideas in this area that haven't
occurred to us, but the reverse is even more likely. In any case,
segmentation by optimization is a solution in search of a problem; as
stated in the first sentence of this subsection, a real image needs to
be segmented into parts that correspond to different objects in the scene,
not into an "optimal" set of regions.
In my opinion, there are good reasons for the often-lamented lack of
interaction between CG and CV. The CG community is welcome to look
for geometric problems that CV appears to suggest, but they shouldn't
expect that the CV community will rush to adopt their solutions.