- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Models of 2D-scene complexity : a look at the intrinsic...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Models of 2D-scene complexity : a look at the intrinsic complexity of scenes Sauer, Mark R.
Abstract
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.
Item Metadata
Title |
Models of 2D-scene complexity : a look at the intrinsic complexity of scenes
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1999
|
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.
|
Extent |
4555399 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-06-26
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0051215
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1999-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
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.