Data Structures for Incremental Extreme Ray Enumeration Algorithms
Blagoy Genov · 2013
Given a halfspace H and a polyhedral cone P with a known extreme ray set V we consider the problem of finding the extreme ray set for the cone P ′ = H ∩ P. Regarding the computational time of the above prob-lem, best results have been achieved with data struc-tures based on multidimensional binary search trees. We refined the existing algorithm by developing a spe-cific method for tree creation which brought further computational speedup. Furthermore, we examined al-ternative data structures based on vantage point trees and identified potential scenarios for their application. 1