Time and space tradeoffs in point location

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.

Name thesis:degree_name

M.S. (Master of Science)

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science (UMKC)

Grantor

University of Missouri--Kansas City

Year dc:date.issued

2024

Author dc:creator

• Gonuguntla, Mounika

Advisor dc:contributor.advisor

• Han, Yijie, 1959-

Handle dc:identifier.uri

https://hdl.handle.net/10355/101208

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/101208