Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore real numbers can not be faithfully represented by finite strings over a finite alphabet.
Unlike the classical computability over finite strings where different models of computation like: lambda calculus, Turing machines, recursive functions, ... turn out to be equivalent (at least for computability over functions on strings), there are various proposed models for computation over real numbers which are not compatible. For example, in the TTE model (see also [Wei00]) which is the closest one to the classical Turing machine model, the real numbers are represented using infinite input tapes (like Turing's oracles) and it is not possible to decide the comparison and equality relations between two given real numbers (in finite amount of time). On the other hand in the BBS/real-RAM models which are similar to RAM machine model, we have variables that can store arbitrary real numbers, and comparison and equality are among the atomic operations of the model. For this and similar reasons many experts say that the BSS/real-RAM models are not realistic (cannot be implemented, at least not on current digital computers), and they prefer the TTE or other equivalent models to TTE like effective domain theoretic model, Ko-Friedman model, etc.
If I understood correctly, the default model of computation which is used in Computational Geometry is the BSS (a.k.a. real-RAM, see [BCSS98]) model.
On the other hand, it seems to me that in the implementation of the algorithms in Computational Geometry (e.g. LEDA), we are only dealing with algebraic numbers and no higher-type infinite objects or computations are involved (is this correct?). So it appears to me (probably naively) that one can also use the classical model of computation over finite strings to deal with these numbers and use the usual model of computation (which is also used for implementation of the algorithms) to discuss correctness and complexity of algorithms.
Questions:
What are the reasons that researchers in Computational Geometry prefer to use the BSS/real-RAM model? (reasons specific Computational Geometry for using the BSS/real-RAM model)
What are the problems with the (probably naive) idea that I have mentioned in the previous paragraph? (using the classic model of computation and restricting the inputs to algebraic numbers in Computational Geometry)
Addendum:
There is also the complexity of algorithms issue, it is very easy to decide the following problem in the BSS/real-RAM model:
Given two sets $S$ and $T$ of positive integers,
is $\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$?
While no efficient integer-RAM algorithm is known for solving it. Thanks to JeffE for the example.
References:
- Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, "Complexity and Real Computation", 1998
- Klaus Weihrauch, "Computable Analysis, An Introduction", 2000