Time and space tradeoffs in point location
No Thumbnail Available
Authors
Meeting name
Sponsors
Date
Journal Title
Format
Subject
Abstract
We preprocess the input subdivision with n points on the plane in O(n√log n) time and store them in O(n/t) space to facilitate point location in O(log t) time, where t is an adjustable parameter. When t is a constant we get O(n) space and constant time. When t = O(n) we get constant space and O(log n) time.
Table of Contents
Introduction -- The O(N√log N) time sorting algorithm for sorting real numbers -- Point location -- Main theorem -- Conclusions
DOI
PubMed ID
Degree
M.S. (Master of Science)