Enumerating extreme rays of a cone
Shaojie Chang, Katta G. Murty, Marsha Chang, Hye Jin Hwang · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We consider the problem of identifying all extreme rays of the polyhedral cone defined as the nonnegative hull of a specified set of points. Such cone may or may not have any extreme ray. Hence, we need to be able to check whether the cone has any extreme ray and enumerate all the extreme rays if the given cone has any. For the cases in 4 or higher dimensions, we developed a linear programming model for checking the existence of the extreme ray in the given cone. For the cases in three dimensions, we develop an algorithm which can enumerate all the extreme rays of the given cone. This algorithm has the worst case complexity of O(m log m) where m is the number of given points.