Output-sensitive construction of convex hulls
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Chan, Timothy Moon-Yew
issued: 2009-04-15T23:47:29Z
issued: 1995
related degree: Doctor of Philosophy - PhD
degree grantor: University of British Columbia
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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/7188
extent: 1699842 bytes
format: application/pdf
note: OUTPUT-SENSITIVE CONSTRUCTION OF CONVEX HULLSByTIMOTHY MOON-YEW CHANB.A., Rice University, 1992A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF COMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAOctober, 1995© Timothy Moon-Yew Chan, 1995In presenting this thesis in partial fulfilment of the requirements foran advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be ‘granted by the head of mydepartment or by his or her representatives. It is understoodthat copying orpublication of this thesis for financial gain shall not be allowed withoót my writtenpermission;(Signature)Department of Comput-r cneThe University of British ColumbiaVancouver, CanadaDate October 4, 1995DE-6 (2)88)AbstractThe construction of the convex hull of a finite point set in a low-dimensional Euclideanspace is a fundamental problem in computational geometry. This thesis investigatesefficient algorithms for the convex hull problem, where complexity is measured as afunction 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 polylogarithmic factor of optimal. In higher fixed dimensions, we obtain an algorithm thatis optimal for sufficiently small output sizes and is faster than previous methods forsublinear output sizes; this result is further improved in even dimensions.Although the focus of the thesis is on the convex hull problem, applications of ourtechniques to many related problems in computational ge…
has type: Thesis/Dissertation
date issued: 1995-11
is shown at: 10.14288/1.0051478
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
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.
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/7188