It is used in various applications such as visualisation, solid modelling, and surface simplification. In practice, the algorithm for architectural models constructs a smaller binary space partition than most known algorithms. I also developed the first provably-efficient algorithm for maintaining a binary space partition for a set of moving segments in the plane. I developed the object complexity model for hidden-surface removal. I am currently implementing a new algorithm for hidden-surface removal in walkthrough applications that renders complex environments efficiently by maintaining a small superset of the set of visible objects.
Geometric data repair Many geometric data sets contain geometric and topological errors.
I developed and implemented a novel approach based on spatial partitions for generating topologically-consistent solid models from arbitrary polygonal data. An important problem in geographic information systems is computing the contour of a terrain at a given height. Since terrain data sets often do not fit in main memory, algorithms operating on them should minimise the number of disk accesses they perform. I developed the first algorithm for contour extraction that uses an optimal number of disk accesses. Algebraic decision trees Constructing algebraic decision trees is a fundamental machine learning problem.