Back to results

University of Waterloo

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Abstract

dc:description.abstract

Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this thesis, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including: - An output-sensitive algorithm that computes the maxima for a set of n points in two dimensions using 1n log(h) + O(n sqrt(log(h))) comparisons, where h is the size of the output. - A randomized algorithm that computes the maxima in three dimensions that uses 1n log(n) + O(n sqrt(log(n))) expected number of comparisons. - A randomized output-sensitive algorithm that computes the maxima in three dimensions that uses 1n log(h) + O(n log^(2/3)(h)) expected number of comparisons, where h is the size of the output. - An output-sensitive algorithm that computes the convex hull for a set of n points in two dimensions using 1n log(h) + O(n sqrt(log(h))) comparisons and O(n sqrt(log(h))) sidedness tests, where h is the size of the output. - A randomized algorithm for detecting whether of a set of n horizontal and vertical line segments in the plane intersect that uses 1n log(n) +O(n sqrt(log(n))) expected number of comparisons. - A data structure for point location among n axis-aligned disjoint boxes in three dimensions that answers queries using at most (3/2)log(n)+ O(log(log(n))) comparisons. The data structure can be extended to higher dimensions and uses at most (d/2)log(n)+ O(log(log(n))) comparisons. - A data structure for point location among n axis-aligned disjoint boxes that form a space-filling subdivision in three dimensions that answers queries using at most (4/3)log(n)+ O(sqrt(log(n))) comparisons. The data structure can be extended to higher dimensions and uses at most ((d+1)/3)log(n)+ O(sqrt(log(n))) comparisons. Our algorithms and data structures use a variety of techniques, including Seidel and Adamy's planar point location method, weighted binary search, and height-optimal BSP trees.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lee, Patrick

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/8783

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lee, Patrick. On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures. University of Waterloo, 2014. http://hdl.handle.net/10012/8783