Back to search

University of British Columbia

Models of 2D-scene complexity : a look at the intrinsic complexity of scenes

Abstract

dc:description

The worst-case time and space complexity of many algorithms in computational geometry is high when expressed as a function of the input size. This can make algorithms seem inefficient in general. Usually, however, the algorithm will not run with identical times on every input of a given size. Intuitively, inputs of highercomplexity cause higher run-time and/or space costs in an algorithm. The size of an input is only one factor contributing to the complexity of an input. As such, input size is not always an adequate predictor of the behaviour of an algorithm. This thesis looks at models capturing the intrinsic complexity of a scene of objects. The models identify quantifiable properties which can be used as additional parameters in the time and space complexity of computational geometry algorithms. In particular properties of two-dimensional scenes will be explored. One problem is then looked at and analyzed with respect to the new models: the Binary Space Partition problem. Under the assumption that an input scene is considered to be simple by our most general model, the analysis reveals that such a scene will have a linear sized binary space partition.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1999

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sauer, Mark R.

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/9749

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

Sauer, Mark R.. Models of 2D-scene complexity : a look at the intrinsic complexity of scenes. master's thesis, University of British Columbia, 1999. http://hdl.handle.net/2429/9749