TY - THES
AU - Sauer, Mark R.
PY - 1999
TI - Models of 2D-scene complexity : a look at the intrinsic complexity of scenes
KW - Thesis/Dissertation
LA - eng
M3 - Text
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/831/items/1.0051215
ER - End of Reference