# 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}, 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://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6136.html %F Teller:CSD-92-669