Item Details

Selecting Vertices in Arrangements of Hyperplanes

Salowe, Jeffrey
Format
Report
Author
Salowe, Jeffrey
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1987
Published Date
1987
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online