Selecting Vertices in Arrangements of HyperplanesReport
Given any arrangement of n hyperplanes in Rd. there are O(n‘l vertices. This paper shows that the time complexity of selecting the vertex with k‘" smallest z_1-coordinate in such an arrangement is O(nd‘1log3" n), which is sublinear in the number of vertices. This extends the result of from 2 - dimensions to d-dimensions.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Salowe, Jeffrey. "Selecting Vertices in Arrangements of Hyperplanes." University of Virginia Dept. of Computer Science Tech Report (1987).
University of Virginia, Department of Computer Science