Seth J. Teller and Michael E. Hohmeyer

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-669
January 1992

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

We present an algorithm that determines, in expected O( n^2) time, whether a line exists that stabs each of a set of oriented convex polygons in R^3 with a total of n 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 R^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},
    Institution = {EECS Department, University of California, Berkeley},
    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