1
$\begingroup$

In the paper [1], author has discussed a distinction between the 3 types of computations: numeric, combinatorial, and geometric. The author says that Geometric computation is one that has elements of both combinatorial and numeric computation. That is:

Geometric Computing = Numerical + Combinatorial Computing.

Numerical computing is exemplified by the problem of solving linear systems of equations; graph searching is a typical problem of combinatorial computing. The convex hull problem for a set of points is a canonical example of geometric computing: the points are specified by numbers but the convex hull is essentially a combinatorial structure (a labeled graph). Linear programming counts as geometric computing but solving linear systems does not qualify.

I am confused about the last sentence: "Linear Programming counts as geometric computing but solving linear systems does not qualify." Why is that so? We have a perfectly geometric representation of solving linear systems (through intersection of lines and planes). Why is Linear Programming geometric then?

So, my first question is: Why is LP geometric while solving linear systems is not?

Now, in book chapter [2], the author further clarifies:

The mere presence of combinatorial structures in a numerical computation does not make a computation “geometric.” There must be some nontrivial consistency condition holding between the numerical data and the combinatorial data. Thus, we would not consider the classical shortest-path problems on graphs to be geometric: the numerical weights assigned to edges of the graphs are not restricted by any consistency condition. Note that common restrictions on the weights (positivity, integrality, etc.) are not consistency restrictions. But the related Euclidean shortest-path problem (Chapter 31) is geometric.

So, this "consistency condition" seems to be the key distinction to determining if a problem is geometric or not. Could someone shed more light on these consistency conditions?

So, my second question is: What are these consistency conditions that makes a problem geometric?

References:

  • [1] Yap, Chee-Keng. “Towards Exact Geometric Computation".” Computational Geometry, 1997, 21.
  • [2] Sharma, Vikram, and Chee K Yap. “Chapter-45 ROBUST GEOMETRIC COMPUTATION,” Handbook of Discrete and Computational Geometry. Third edition. Boca Raton: CRC Press, 2017.
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You might find the paper Classroom Examples of Robustness Problems in Geometric Computations to be worth a read. They do a nice job illustrating why geometric problems in particular are so difficult. $\endgroup$
    – Daniel Shapero
    Commented Nov 6, 2022 at 22:37
  • $\begingroup$ Thank you @DanielShapero This looks like an accessible paper, aimed at clarifying pretty much my doubt! I will read it. $\endgroup$
    – shivams
    Commented Nov 8, 2022 at 1:58
  • 1
    $\begingroup$ As for question 1: I think you're overthinking this. The author you quote is providing their personal perspective of which box they would put different problems in, but there is certainly a large degree of subjectivity to that. It's not worth trying to spend too much time on such questions. $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 8, 2022 at 16:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.