Xref: utzoo sci.math:12017 comp.graphics:12844
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!snorkelwacker!bu.edu!nntp-xfer.bu.edu!merrill
From: merrill@bucasb.bu.edu (John Merrill)
Newsgroups: sci.math,comp.graphics
Subject: Re: Projection question.
Message-ID: <MERRILL.90Aug14142550@bucasb.bu.edu>
Date: 14 Aug 90 18:25:50 GMT
References: <839@stat.fsu.edu>
Sender: news@bu.edu.bu.edu
Followup-To: sci.math
Organization: Boston University Center for Adaptive Systems
Lines: 38
In-reply-to: naras@stat.fsu.edu's message of 14 Aug 90 17:47:35 GMT

In article <839@stat.fsu.edu> naras@stat.fsu.edu (B. Narasimhan) writes:

> Consider two line segments in R3 determined by points
> (x(1),y(1),z(1)) and (x(2),y(2),z(2)), and (x(3),y(3),z(3)) and
> (x(4),y(4),z(4)) respectively.  I want to project these line
> segments on the XY plane in such a way that I depict which segment
> crosses over and which one goes under. This I can do in a
> straightforward way by computing the intersection point of the
> projected segments (if there is one), then projecting this point
> back to the original line segments and checking the z-coordinate.

> Now suppose I have a sequence of points
> (x(1),y(1),z(1))....(x(n),y(n),z(n)) such that a line segment
> connects (x(i),y(i),z(i)) and (x(i+1),y(i+1),z(i+1)).  The last
> point is connected to (x(1),y(1),z(1)).

> If I use the above approach, I would have an O(n^2) algorithm.

The poster asks: is there a more efficient algorithm?  The answer is
no.

It suffices to observe that there exists a configuration of endpoints
such that the total number of occlusions is O(n^2).  This proves that
the problem is O(n^2)-SPACE, and hence has no solution which is better
than O(n^2)-TIME.   One such configuration of points is constructed by
fixing a k > 0, and taking

(x_{2i}, y_{2i}, z_{2i}) 
   = (cos(pi * i / k), sin(pi * i / k), (2 * i) / k)
and
(x_{2i + 1}, y_{2i + 1}, z_{2i + 1})
   = (cos(pi * (k + i) / k), sin(pi * (k + i) / k), (2 * i + 1) / k)

It is left as a trivial exercise for the reader to prove than there
are O(n^2) occlusions between elements of this polygon when it is
viewed from (0, 0, +\infty).
--
John Merrill / merrill@bucasb.bu.edu / harvard!bu.edu!bucasb!merrill