Created 2007-01-19 Modified 2007-01-21
Chelton Evans
Half Space Intersection Tessellation
Intro
Discussion
Algorithm
Counting the Line Intersections within a Circle
<TODO>
Consider tessellating the space by cutting it up with half spaces and linking these regions together. This is a variation of the incremental algorithm and can be used to slice up the space as each half space is added.
In 2D O(k) can become O(n^2) by considering parallel and perpendicular lines. Two sets of parallel and perpendicular lines with 1 line each divide the plane in 4 regions. Two sets of parallel and perpendicular lines with 2 lines each divide the plane in 9 regions. Two sets of parallel and perpendicular lines with 3 lines each divide the plane in 16 regions. ... This is a quadratic relationship. 2^2=4, 3^2=9, 4^2=16, ...
In 3D O(k) can become cubic.
Consider a set of lines in 2D where none are parallel. Then each line intersects n-1 other lines therefore k=n(n-1) and hence k is quadratic and the algorithm is quadratic.
Consider a set of half spaces in W dimension where none are in
parallel. Each half space intersects n-1 other half spaces therefore
k is quadratic as a minimum.
O(k) = O(n^2) + O(k)
then O(nlogn) + O(k) = O(nlogn) + O(n^2) + O(k) = O(n^2)+O(k)
I conclude that this algorithm is really O(n^2+k).
For a new line being added find its intersection with another line. Cut the mesh with the new line generating the new intersection points and regions.
Finding the region associated with the new intersection point should be O(logn) then generating the intersection points is O(k) as the direction of the line is traveled in the region each new region has the intersection point calculated. Hence the algorithm is O(nlogn+k).
The problem is in the details, linked shapes may be more difficult to manage in 3D.
Consider the problem where given n lines describe a O(nlogn+k) time algorithm that counts the intersections within a circle. k is the number of intersections.
For the circle/sphere restriction all lines/planes can be clipped that do not intersect the circle/sphere. This is O(n) in time.
Assuming that the insertion of the line is O(logn+ki)
and k is accessed thorough the algorithm linearly (upon each insertion
a particular range of k is calculated, since this is unique the sum
of these ranges sum to k). Therefore we can extract the k part of
the equation and each line insertion is in O(logn). Since there
are n such lines the line insertion is O(nlogn). Now add the k
part. O(nlogn+k).
O(n) + O(nlogn+k) = O(nlogn+k)
