Back to search

University of British Columbia

Output-sensitive construction of convex hulls

Abstract

dc:description

The construction of the convex hull of a finite point set in a low-dimensional Euclidean space is a fundamental problem in computational geometry. This thesis investigates efficient algorithms for the convex hull problem, where complexity is measured as a function of both the size of the input point set and the size of the output polytope. Two new, simple, optimal, output-sensitive algorithms are presented in two dimensions and a simple, optimal, output-sensitive algorithm is presented in three dimensions. In four dimensions, we give the first output-sensitive algorithm that is within a poly logarithmic factor of optimal. In higher fixed dimensions, we obtain an algorithm that is optimal for sufficiently small output sizes and is faster than previous methods for sublinear output sizes; this result is further improved in even dimensions. Although the focus of the thesis is on the convex hull problem, applications of our techniques to many related problems in computational geometry are also explored, including the computation of Voronoi diagrams, extreme points, convex layers, levels in arrangements, and envelopes of line segments, as well as problems relating to ray shooting and linear programming.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1995

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chan, Timothy Moon-Yew

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/7188

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Chan, Timothy Moon-Yew. Output-sensitive construction of convex hulls. doctoral thesis, University of British Columbia, 1995. http://hdl.handle.net/2429/7188