[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
1265.0. "Onion Peeling & Massive Paral. terms...?" by CHOVAX::YOUNG (Bush: 'Read my lips; I Lied') Tue Jul 03 1990 05:00
I read this in another conference:
> <<< CIRCUS::SYS$SYSDEVICE:[NOTES$LIBRARY]SRCNOTES.NOTE;1 >>>
>Note 26.11 SRC Activity Reports 11 of 11
. . .
>THEORY [Lyle Ramshaw]
>
> "Onion peeling" is the following process: Given a set of points
> in the plane, find their convex hull, throw out the points that
> lie on that hull, and keep repeating those two steps until no points
> are left. No one knows whether or not onion peeling can be greatly
> speeded up by massive parallelism. John Hershberger has analyzed
> a related problem, in which the layers being peeled are upper
> envelopes of sets of line segments, rather than convex hulls of
> sets of points. He showed that peeling upper envelopes is a
> P-complete problem, which is good evidence that it cannot be done
> fast in parallel.
... and I found it interesting, but I was stymied by some of the
terminology. Can any one help me with these?
IE.:
1) What exactly is the problem to be solved in "Onion Peeling"?
Is it to assign a Hull number to every point? Or to determine the
set of points that constitute the innermost Hull?
2) What does the term "greatly speeded up by massive parrallelism"
mean? What is the quality (or quantity) of speedup implied by
this? What does the later phrase "done fast in parallel" mean?
(The same thing?)
3) What are "upper envelopes of sets of line segments"?
I tried to coantact John Hershberger himself today, but he is out until
the 17th. Can anyone help with these until then?
-- Barry
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1265.1 | | GUESS::DERAMO | Colorado Rocky Mountain high | Tue Jul 03 1990 14:18 | 9 |
| >> 3) What are "upper envelopes of sets of line segments"?
Perhaps the convex hull of the points of intersection
and endpoints of the segments. What I thought of when
I saw the term was a parabola with say a dozen tangents
drawn against it, making the outline of a polygon that
"hugs" the parabola.
Dan
|
| 1265.2 | iterated hulls... | ALLVAX::JROTH | It's a bush recording... | Fri Jul 06 1990 20:25 | 21 |
| I'm not sure of the exact "practical" use of onion peeling, though it is
somewhat related to gift wrapping for determining convex hulls in
reverse. It is sometimes referred to as the "iterated hull".
I believe the best known time is O(n log(n)^2) to get the onion of
a set of points.
Probably it is being studied because it sheds light on some
fundamental complexity issues in computational geometry.
The upper envelopes of line segments is just what one would think
it is - kind of an upper convex hull. This is if interest because
of the popularity of plane-sweep algorithms. If it could be
determined very efficiently, then plane sweeping could be done
faster.
I assume the interest in parallelism comes from things like the
connection machine. A lot of practical problems such as VLSI layout
and routine would be sped quite a bit in practice if they were
amenable to running on parallel processors.
- Jim
|
| 1265.3 | Got some answers... | CHOVAX::YOUNG | Bush: 'Read my lips; I Lied' | Sat Jul 07 1990 16:04 | 14 |
| I talked to Lyle Ramshaw yesterday and got answers to most of my
questions, especially what is meant by "Fast in Parallel".
Apparently a problem may be considered "Fast" in parallel if it can be
done in "Polylog" time with an arbitrarily large number of processors.
"Polylog" means O(log(n)^k) where (k) may be any positive constant.
Re .2:
O(n log(n)^2) is pretty good. Do you have any idea how this algorithim
works? The best that I could come up with was O(n^2 log(n)).
-- Barry
|