<p>It is not quite true that the real RAM / BSS model is equivalent to the algebraic computation tree model. The latter is more powerful because a polynomial depth tree can be of exponential size. This gives a lot of room for encoding non-uniform information.
For instance,  Meyer auf der Heide has shown that algebraic (even linear) decision trees can solve efficiently hard problems such as subset sum, but this is (conjecturally) impossible in the real RAM / BSS model.</p>

CC BY-SA 2.5
2010-10-13T14:25:07.217Z
Excellent point!!
Jeffε
CC BY-SA 2.5
2010-10-13T13:51:16.120Z
2010-10-13T13:51:16.120Z
Pascal Koiran
<p>Here is a comment on Jeff's excellent answer:</p>

<p>Notions of condition, approximation and round-off were proposed to address the complexity gap (combinatorial vs. continuous ) of linear programming algorithms. The condition of a problem instance estimates the effect of small perturbations of the input on the accuracy of the output. The notion of condition was first introduced by Alan Turing. Jim Renegar introduced the notion of condition of a linear program.</p>

<p>L. BLUM,<a href="http://www.ams.org/notices/200409/fea-blum.pdf" rel="noreferrer">Computing over the
Reals: Where Turing
Meets Newton,
</a>
<a href="http://www.ams.org/notices/200409/fea-blum.pdf" rel="noreferrer">,</a> NOTICES OF THE AMS, VOLUME 51, NUMBER 9,  (2004), 1024-1034</p>

<p>A. TURING, Rounding-off errors in matrix
processes, Quart. J. Mech. Appl. Math. 1 (1948),
287–308</p>

<p>J. RENEGAR, Incorporating condition numbers
into the complexity theory of linear programming,
SIAM J. Optim. 5 (1995), 506–524</p>

<p>F. CUCKER, and J. PEÑA, A primal-dual algorithm
for solving polyhedral conic systems with
a finite-precision machine, SIAM Journal on Optimization
12 (2002), 522–554.</p>

CC BY-SA 2.5
2010-10-12T08:14:21.303Z
2010-10-12T08:14:21.303Z
Mohammad Al-Turkistany
<p>First of all, computational geometers don't think of it as the BSS model.  The real RAM model  was defined by Michael Shamos in his 1978 PhD thesis (<em>Computational Geometry</em>), which arguably launched the field.  Franco Preparata revised and extended Shamos' thesis into the first computational geometry textbook, published in 1985.  The real RAM is also equivalent (<em>except for uniformity; see Pascal's answer!</em>) to the <em>algebraic computation tree</em> model defined by Ben-Or in 1983.  Blum, Shub, and Smale's efforts were published in 1989, well after the real-RAM had been established, and were almost completely ignored by the computational geometry community.</p>

<p>Most (classical) results in computational geometry are heavily tied to issues in <em>combinatorial</em> geometry, for which assumptions about coordinates being integral or algebraic are (at best) irrelevant distractions.  Speaking as a native, it seems completely natural to consider <em>arbitrary</em> points, lines, circles, and the like <em>as first class objects</em> when proving things about them, and therefore equally natural when designing and analyzing algorithms to compute with them.</p>

<p>For most (classical) geometric algorithms, this attitude is reasonable even in practice.  Most algorithms for planar geometric problems are built on top of a very small number of geometric primitives: Is point $p$ to the left or right of point $q$?  Above, below, or on the line through points $q$ and $r$?  Inside, outside, or on the circle determined by points $q,r,s$?  Left or right of the intersection of segments $qr$ and $st$?  Each of these primitives is implemented by evaluating the sign of a low-degree polynomial in the input coordinates.  (So these algorithms can be described in the weaker algebraic <em>decision</em> tree model.)  If the input coordinates happen to be integers, these primitives can be evaluated exactly with only constant-factor increase in precision, and so running times on the real RAM and the integer RAM are the same.</p>

<p>For similar reasons, when most people think about sorting algorithms, they don't care <em>what</em> they're sorting, as long as the data comes from a totally ordered universe and any two values can be compared in constant time.</p>

<p>So the community developed a separation of concerns between the design of “real” geometric algorithms and their practical implementation; hence the development of packages like LEDA and  CGAL.  Even for people working on exact computation, there is a distinction between the <em>real</em> algorithm, which uses exact real arithmetic as part of the underlying model, and the <em>implementation</em>, which is forced by the otherwise irrelevant limitations of physical computing devices to use discrete computation.</p>

<p>Within this worldview, for example, the most important open problem in computational geometry is the existence of a polynomial-time algorithm for linear programming.  No, the ellipsoid and interior-point methods don't count.  Unlike the simplex algorithm, those algorithms aren't guaranteed to terminate unless the constraint matrix happens to be rational.  (<a href="http://en.wikipedia.org/wiki/Mnev%27s_universality_theorem">There are combinatorial types of convex polytopes that can only be represented by irrational constraint matrices</a>, so this <em>is</em> a nontrivial restriction.)  And even when the constraint matrix is rational, the running times of those algorithms aren't bounded by <em>any</em> function of the input size (dimension$\times$#constraints).</p>

<p>There are a few geometric algorithms that really do rely heavily on the algebraic <em>computation</em> tree model, and therefore <em>cannot</em> be implemented exactly and efficiently on physical computers.  One good example is minimum-link paths in simple polygons, which can be computed in linear time on a real RAM, but <a href="http://portal.acm.org/citation.cfm?id=237342">require a quadratic number of bits</a> in the worst-case to represent exactly.  Another good example is Chazelle's <a href="http://www.cs.princeton.edu/~chazelle/pubs/CuttingHyperplanes.pdf">hierarchical cuttings</a>, which are used in the most efficient <a href="http://portal.acm.org/citation.cfm?id=142732">algorithms</a> known for <a href="http://en.wikipedia.org/wiki/Range_searching">simplex range searching</a>.  These cuttings use a hierarchy of sets of triangles, where the vertices of triangles at each level are intersection points of lines through edges of triangles at previous levels.  Thus, even if the input coordinates are integers, the vertex coordinates for these triangles are algebraic numbers of unbounded degree; nevertheless, the algorithms for constructing and using cuttings assume that coordinates can be manipulated exactly in constant time.</p>

<p>So, my short, personally biased answer is this: TTE, domain theory, Ko-Friedman, and other models of “realistic” real-number computation all address issues that the computational geometry community, on the whole, just doesn't care about.</p>

CC BY-SA 2.5
2010-10-12T07:21:17.527Z
Perhaps it should be added that, while on the whole successful, this point of view has led to a few weird distortions in which e.g. multiple-polylog(n) parametric searching algorithms are preferred to much simpler log(numerical precision) binary searching algorithms.
David Eppstein
CC BY-SA 2.5
2010-10-12T15:18:22.010Z
It's interesting that you should mention sorting, since the restriction of attention to totally ordered domains yields the classic $\Omega(n \log n)$ lower bound, which can be beaten by breaking that abstraction barrier (see http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction for more). Are there any such examples in computational geometry?
Joshua Grochow
CC BY-SA 2.5
2010-10-12T15:54:29.757Z
Joshua: yes, see e.g. http://arxiv.org/abs/1010.1948
David Eppstein
CC BY-SA 2.5
2010-10-12T18:57:35.637Z
@David Eppstein: very interesting! Would you like to post it as an answer to my other question: http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction
Joshua Grochow
CC BY-SA 2.5
2010-10-12T05:56:40.377Z
2010-10-13T14:23:40.263Z
2010-10-13T14:23:40.263Z
Jeffε
<h3>Background</h3>
<p>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.</p>
<p>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 <a href="http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/" rel="nofollow noreferrer">TTE</a> 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 BSS/real-RAM models which are similar to <a href="http://en.wikipedia.org/wiki/Random-access_machine" rel="nofollow noreferrer">RAM machine model</a>, 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.</p>
<p>If <a href="https://cstheory.stackexchange.com/questions/2058/how-are-real-numbers-specified-in-computation/2070#2070">I understood correctly</a>, the default model of computation which is used in <a href="http://en.wikipedia.org/wiki/Computational_geometry" rel="nofollow noreferrer">Computational Geometry</a> is the <a href="http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow noreferrer">BSS</a> (a.k.a. <a href="http://en.wikipedia.org/wiki/Real_RAM" rel="nofollow noreferrer">real-RAM</a>, see [BCSS98]) model.</p>
<p>On the other hand, it seems to me that in the implementation of the algorithms in Computational Geometry (e.g. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.5812&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">LEDA</a>), 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.</p>
<hr />
<h3>Questions:</h3>
<blockquote>
<p>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)</p>
<p>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)</p>
</blockquote>
<hr />
<h3>Addendum:</h3>
<p>There is also the complexity of algorithms issue, it is very easy to decide the following problem in the BSS/real-RAM model:</p>
<blockquote>
<p>Given two sets <span class="math-container">$S$</span> and <span class="math-container">$T$</span> of positive integers,<br />
is <span class="math-container">$\sum_{s\in S} \sqrt{s} &gt; \sum_{t\in T}\sqrt{t}$</span>?</p>
</blockquote>
<p>While no efficient integer-RAM algorithm is known for solving it. Thanks to JeffE for the example.</p>
<hr />
<p>References:</p>
<ol>
<li>Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, &quot;Complexity and Real Computation&quot;, 1998</li>
<li>Klaus Weihrauch, &quot;<a href="http://www.fernuni-hagen.de/weihrauch/index_data/book.html" rel="nofollow noreferrer">Computable Analysis, An Introduction</a>&quot;, 2000</li>
</ol>

CC BY-SA 2.5
2010-10-12T06:53:32.597Z
By the way, in case it isn't obvious, the sum of square roots problem has a very natural geometric interpretation: it is what you need to solve if you want to compare the lengths of two polygonal paths with integer-coordinate vertices.
David Eppstein
<cc.complexity-theory><cg.comp-geom><computing-over-reals><computable-analysis>
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Kaveh
# What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

(Asked by: username_0 on 2010-10-11)

### 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](http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/) 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 BSS/real-RAM models which are similar to [RAM machine model](http://en.wikipedia.org/wiki/Random-access_machine), 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](https://cstheory.stackexchange.com/questions/2058/how-are-real-numbers-specified-in-computation/2070#2070), the default model of computation which is used in [Computational Geometry](http://en.wikipedia.org/wiki/Computational_geometry) is the [BSS](http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) (a.k.a. [real-RAM](http://en.wikipedia.org/wiki/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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.5812&rep=rep1&type=pdf)), 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:

1. Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, "Complexity and Real Computation", 1998
2. Klaus Weihrauch, "[Computable Analysis, An Introduction](http://www.fernuni-hagen.de/weihrauch/index_data/book.html)", 2000

**Tags:** cc.complexity-theory, cg.comp-geom, computing-over-reals, computable-analysis
> **Comments:**
> **username_1**: By the way, in case it isn't obvious, the sum of square roots problem has a very natural geometric interpretation: it is what you need to solve if you want to compare the lengths of two polygonal paths with integer-coordinate vertices.  

---

## 3 answers

### Answer by username_3 on 2010-10-12. Score: 47 | Accepted answer

First of all, computational geometers don't think of it as the BSS model. The real RAM model was defined by Michael Shamos in his 1978 PhD thesis (*Computational Geometry*), which arguably launched the field. Franco Preparata revised and extended Shamos' thesis into the first computational geometry textbook, published in 1985. The real RAM is also equivalent (*except for uniformity; see Pascal's answer!*) to the *algebraic computation tree* model defined by Ben-Or in 1983. Blum, Shub, and Smale's efforts were published in 1989, well after the real-RAM had been established, and were almost completely ignored by the computational geometry community.

Most (classical) results in computational geometry are heavily tied to issues in *combinatorial* geometry, for which assumptions about coordinates being integral or algebraic are (at best) irrelevant distractions. Speaking as a native, it seems completely natural to consider *arbitrary* points, lines, circles, and the like *as first class objects* when proving things about them, and therefore equally natural when designing and analyzing algorithms to compute with them.

For most (classical) geometric algorithms, this attitude is reasonable even in practice. Most algorithms for planar geometric problems are built on top of a very small number of geometric primitives: Is point $p$ to the left or right of point $q$? Above, below, or on the line through points $q$ and $r$? Inside, outside, or on the circle determined by points $q,r,s$? Left or right of the intersection of segments $qr$ and $st$? Each of these primitives is implemented by evaluating the sign of a low-degree polynomial in the input coordinates. (So these algorithms can be described in the weaker algebraic *decision* tree model.) If the input coordinates happen to be integers, these primitives can be evaluated exactly with only constant-factor increase in precision, and so running times on the real RAM and the integer RAM are the same.

For similar reasons, when most people think about sorting algorithms, they don't care *what* they're sorting, as long as the data comes from a totally ordered universe and any two values can be compared in constant time.

So the community developed a separation of concerns between the design of “real” geometric algorithms and their practical implementation; hence the development of packages like LEDA and CGAL. Even for people working on exact computation, there is a distinction between the *real* algorithm, which uses exact real arithmetic as part of the underlying model, and the *implementation*, which is forced by the otherwise irrelevant limitations of physical computing devices to use discrete computation.

Within this worldview, for example, the most important open problem in computational geometry is the existence of a polynomial-time algorithm for linear programming. No, the ellipsoid and interior-point methods don't count. Unlike the simplex algorithm, those algorithms aren't guaranteed to terminate unless the constraint matrix happens to be rational. ([There are combinatorial types of convex polytopes that can only be represented by irrational constraint matrices](http://en.wikipedia.org/wiki/Mnev%27s_universality_theorem), so this *is* a nontrivial restriction.) And even when the constraint matrix is rational, the running times of those algorithms aren't bounded by *any* function of the input size (dimension$\times$#constraints).

There are a few geometric algorithms that really do rely heavily on the algebraic *computation* tree model, and therefore *cannot* be implemented exactly and efficiently on physical computers. One good example is minimum-link paths in simple polygons, which can be computed in linear time on a real RAM, but [require a quadratic number of bits](http://portal.acm.org/citation.cfm?id=237342) in the worst-case to represent exactly. Another good example is Chazelle's [hierarchical cuttings](http://www.cs.princeton.edu/~chazelle/pubs/CuttingHyperplanes.pdf), which are used in the most efficient [algorithms](http://portal.acm.org/citation.cfm?id=142732) known for [simplex range searching](http://en.wikipedia.org/wiki/Range_searching). These cuttings use a hierarchy of sets of triangles, where the vertices of triangles at each level are intersection points of lines through edges of triangles at previous levels. Thus, even if the input coordinates are integers, the vertex coordinates for these triangles are algebraic numbers of unbounded degree; nevertheless, the algorithms for constructing and using cuttings assume that coordinates can be manipulated exactly in constant time.

So, my short, personally biased answer is this: TTE, domain theory, Ko-Friedman, and other models of “realistic” real-number computation all address issues that the computational geometry community, on the whole, just doesn't care about.

> **Comments:**
> **username_1**: Perhaps it should be added that, while on the whole successful, this point of view has led to a few weird distortions in which e.g. multiple-polylog(n) parametric searching algorithms are preferred to much simpler log(numerical precision) binary searching algorithms.  
> **username_5**: It's interesting that you should mention sorting, since the restriction of attention to totally ordered domains yields the classic $\Omega(n \log n)$ lower bound, which can be beaten by breaking that abstraction barrier (see http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction for more). Are there any such examples in computational geometry?  
> **username_1**: Joshua: yes, see e.g. http://arxiv.org/abs/1010.1948  
> **username_5**: @David Eppstein: very interesting! Would you like to post it as an answer to my other question: http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction  

---

### Answer by username_2 on 2010-10-13. Score: 16

It is not quite true that the real RAM / BSS model is equivalent to the algebraic computation tree model. The latter is more powerful because a polynomial depth tree can be of exponential size. This gives a lot of room for encoding non-uniform information.
For instance, Meyer auf der Heide has shown that algebraic (even linear) decision trees can solve efficiently hard problems such as subset sum, but this is (conjecturally) impossible in the real RAM / BSS model.

> **Comments:**
> **username_3**: Excellent point!!  

---

### Answer by username_4 on 2010-10-12. Score: 5

Here is a comment on Jeff's excellent answer:

Notions of condition, approximation and round-off were proposed to address the complexity gap (combinatorial vs. continuous ) of linear programming algorithms. The condition of a problem instance estimates the effect of small perturbations of the input on the accuracy of the output. The notion of condition was first introduced by Alan Turing. Jim Renegar introduced the notion of condition of a linear program.

L. BLUM,[Computing over the
Reals: Where Turing
Meets Newton,](http://www.ams.org/notices/200409/fea-blum.pdf)
[,](http://www.ams.org/notices/200409/fea-blum.pdf) NOTICES OF THE AMS, VOLUME 51, NUMBER 9, (2004), 1024-1034

A. TURING, Rounding-off errors in matrix
processes, Quart. J. Mech. Appl. Math. 1 (1948),
287–308

J. RENEGAR, Incorporating condition numbers
into the complexity theory of linear programming,
SIAM J. Optim. 5 (1995), 506–524

F. CUCKER, and J. PEÑA, A primal-dual algorithm
for solving polyhedral conic systems with
a finite-precision machine, SIAM Journal on Optimization
12 (2002), 522–554.


---

