Seth J. Teller and Michael E. Hohmeyer

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-669

, 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-669.pdf

We present an algorithm that determines, in expected <i>O</i>(<i>n</i>^2) time, whether a line exists that stabs each of a set of oriented convex polygons in <i>R</i>^3 with a total of <i>n</i> edges. If a stabbing line exists, the algorithm computes at least one such line. We show that the computation amounts to constructing a convex polytope in <i>R</i>^5 and inspecting its edges for intersections with a four-dimensional quadric surface, the Plucker quadric.

---

BibTeX citation:

@techreport{Teller:CSD-92-669,
    Author= {Teller, Seth J. and Hohmeyer, Michael E.},
    Title= {Stabbing Oriented Convex Polygons in Randomized O(n^2) Time},
    Year= {1992},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6136.html},
    Number= {UCB/CSD-92-669},
    Abstract= {We present an algorithm that determines, in expected <i>O</i>(<i>n</i>^2) time, whether a line exists that stabs each of a set of oriented convex polygons in <i>R</i>^3 with a total of <i>n</i> edges. If a stabbing line exists, the algorithm computes at least one such line. We show that the computation amounts to constructing a convex polytope in <i>R</i>^5 and inspecting its edges for intersections with a four-dimensional quadric surface, the Plucker quadric.},
}

EndNote citation:

%0 Report
%A Teller, Seth J. 
%A Hohmeyer, Michael E. 
%T Stabbing Oriented Convex Polygons in Randomized O(n^2) Time
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-669
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6136.html
%F Teller:CSD-92-669