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