Time, Space, and Precision: Revisiting Classic Problems in Computational Geometry with Degree-Driven Analysis, pp. 280.
Jack Scott Snoeyink · Canadian Conference on Computational Geometry · 2014
Computational geometry, as a branch of the theory of computer science, designs and analyzes data structures and algorithms most often for a RealRAM model, which has three unbounded quantities: the time its program can run, the number of memory cells, and the number of bits that can be stored in each cell. Since actual computers have constraints for time and memory — constraints that change as technology advances — we follow the computer science tradition of developing our algorithms to minimize time and memory size, measured using the familiar asymptotic, big-O notation, and tacitly agreeing not to exploit the third unbounded quantity in our model. (Exceptions published with capitalized words in the title [3] merely prove the rule.)