40
$\begingroup$

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:

  1. Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, "Complexity and Real Computation", 1998
  2. Klaus Weihrauch, "Computable Analysis, An Introduction", 2000
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 12 '10 at 6:53
42
$\begingroup$

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, 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 in the worst-case to represent exactly. Another good example is Chazelle's hierarchical cuttings, which are used in the most efficient algorithms known for simplex 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.

$\endgroup$
  • 9
    $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 12 '10 at 7:21
  • $\begingroup$ 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 cstheory.stackexchange.com/questions/608/… for more). Are there any such examples in computational geometry? $\endgroup$ – Joshua Grochow Oct 12 '10 at 15:18
  • 4
    $\begingroup$ Joshua: yes, see e.g. arxiv.org/abs/1010.1948 $\endgroup$ – David Eppstein Oct 12 '10 at 15:54
  • 1
    $\begingroup$ @David Eppstein: very interesting! Would you like to post it as an answer to my other question: cstheory.stackexchange.com/questions/608/… $\endgroup$ – Joshua Grochow Oct 12 '10 at 18:57
15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Excellent point!! $\endgroup$ – Jeffε Oct 13 '10 at 14:25
4
$\begingroup$

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, , 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.