Selecting Vertices in Arrangements of Hyperplanes
ReportAuthor:Salowe, Jeffrey, Department of Computer ScienceUniversity of Virginia
Abstract:
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
Rights:
All rights reserved (no additional license for public reuse)
All rights reserved (no additional license for public reuse)
Language:
English
English
Source Citation:
Salowe, Jeffrey. "Selecting Vertices in Arrangements of Hyperplanes." University of Virginia Dept. of Computer Science Tech Report (1987).
Publisher:
University of Virginia, Department of Computer Science
University of Virginia, Department of Computer Science
Published Date:
1987
1987
