[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

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 01: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.RTitleUserPersonal
Name		DateLines
1265.1GUESS::DERAMOColorado Rocky Mountain highTue Jul 03 1990 10:189
>>    	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.2iterated hulls...ALLVAX::JROTHIt&#039;s a bush recording...Fri Jul 06 1990 16:2521
   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.3Got some answers...CHOVAX::YOUNGBush: &#039;Read my lips; I Lied&#039;Sat Jul 07 1990 12:0414
    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