Publication:
Selecting Vertices in Arrangements of Hyperplanes

Thumbnail Image

Files

TR-87-19.pdf (1.7 MB)

Date

1987-01-01

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

University of Virginia, Department of Computer Science

Research Projects

Organizational Units

Journal Issue

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

Description

Original submission date: 2013-10-11T18:17:17Z

Subjects

Citation

Salowe, Jeffrey. "Selecting Vertices in Arrangements of Hyperplanes." University of Virginia Dept. of Computer Science Tech Report (1987).

URI

https://doi.org/10.18130/V37N4J
 https://libraopen.library.virginia.edu/handle/item/9383

Collections

Computer Science

Endorsement

Review

Supplemented By

Referenced By