Stabbing Oriented Convex Polygons in Randomized O(n^2) Time
Seth J. Teller and Michael E. Hohmeyer
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-669
January 1992
http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6136.html},
Number = {UCB/CSD-92-669}
}
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://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6136.html %F Teller:CSD-92-669