28
$\begingroup$

One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think of a triplet of numbers as a point in 3-d and hence computation about triplets of numbers as computation about points in 3-d, which can then be solved using our intuition about space. This seems to suggest that it should be possible at times to solve a completely non-geometric problem using techniques from geometry. Does anyone know of such examples?

Of course, the terms 'geometric' and 'non-geometric' are slightly vague here. One can argue that any geometric problem is actually non-geometric if you replace all points with their co-ordinates. But intuitively, the definition is clear. Let's just say that we call something geometric if we would consider sending a paper about it to SoCG.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Of course the grand-daddy of this is the P vs NP approach outlined by Mulmuley, which is purely geometric. But it hasn't proved useful yet. The proof separating P from NC without bitwise operations is however a non-geometric proof that uses geometric arguments. I'd add that, but I've supplied too many answers already :) $\endgroup$
    – Suresh Venkat
    May 9, 2011 at 5:23
  • $\begingroup$ plenty of such examples can be found in the proofs without words section of American Mathematical Monthly $\endgroup$
    – jimjim
    May 9, 2011 at 10:46

17 Answers 17

Reset to default
24
$\begingroup$

A few more examples:

Sleator, Thurston and Tarjan used a geometric representation of trees as partitions of polygons, and hyperbolic geometry, to prove lower bounds for binary tree rotation. (Also, I believe the history of a dynamic binary search tree can be represented as a tetrahedralization.)

The reduction of least common ancestor to range minimum queries, due to Berkman and Vishkin, relates a data structures problem on trees to an arguably-geometric problem. (and thanks for the article David)

The reduction of a scheduling problem to max weight independent set of axis-parallel rectangles [1] or the reduction of a different scheduling problem to geometric set cover [2] might qualify.

The reduction of the largest common subsequence problem to finding layers of maxima is well-known (meaning, I'm too lazy to look up who actually thought of it).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor and Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.

[later edit] A couple more cases where a "geometric" view seemed surprising (though the "submission to SoCG" or "makes something to visualize" standards are probably not met):

algebraic topology applied to lower bounds for distributed computing

incorporating computability into Hausdorff dimension

defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Nikhil's paper is a very interesting example, that I somehow forgot about. $\endgroup$
    – Sasho Nikolov
    May 10, 2011 at 19:23
  • 3
    $\begingroup$ Welcome to cstheory, Ken :) $\endgroup$
    – Suresh Venkat
    May 10, 2011 at 20:17
  • 1
    $\begingroup$ Nobody seems to mention the planar separator theorem... Which turns out to be an easy consequence of Koebe theorem. $\endgroup$
    – Sariel Har-Peled
    May 15, 2011 at 19:16
  • 2
    $\begingroup$ I am surprised no one mentioned the equivalence of optimization and separation for linear programming and its impact on combinatorial optimization. The book of Grotschel, Lovasz and Schrijver is titled "Geometric Algorithms and Combinatorial Optimization". $\endgroup$
    – Chandra Chekuri
    May 16, 2011 at 3:09
  • 1
    $\begingroup$ The two important papers relating algebraic topology to distributed computing (that won 2004 Gödel Prize) are: * Maurice Herlihy and Nir Shavit, “The Topological Structure of Asynchronous Computability,” JACM 46, 6 (1999). * Michael Saks and Fotios Zaharoglou, “Wait-Free k-Set Agreement Is Impossible: the Topology of Public Knowledge,” SIAM J. Computing 29, 5 (2000). $\endgroup$
    – didest
    Jun 3, 2011 at 21:45
15
$\begingroup$

Of course a much better answer than my previous one is the use of metric embedding theory for solving sparsest cut. A key step in the solution to the sparsest cut problem was the realization that it could be approximated by finding a good embedding of a general metric into an $\ell_1$-normed space.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you please cite the paper? $\endgroup$
    – user
    Mar 17, 2014 at 23:56
  • 1
    $\begingroup$ @user here you go. $\endgroup$
    – Suresh Venkat
    Mar 18, 2014 at 0:10
12
$\begingroup$

Those were mentioned somewhere else too, but an example I like is this: sorting with partial information is the problem of finding a fixed unknown linear extension of a poset, given the poset and using number of comparison queries as close as possible to the information theoretic lower bound (this is just sorting when the number of comparisons is the critical complexity measure and some comparisons are given for free). The existence of optimal (up to a constant) comparison strategies was proven by Saks and Kahn using the properties of the order polytope, a special polytope associated with a poset (you can find a great exposition in Matousek's Lectures on Discrete Geometry book). The first polynomial time algorithm (by Kahn and Kim) that computes an optimal (up to a constant) comparison strategy again used the properties of the order polytope as well as the stable set polytope of the incomparability graph of the input poset.

Improve this answer
$\endgroup$
11
$\begingroup$

There's a relatively recent paper by Demaine et al that uses a geometric representation of binary search trees to advance the state of the art on dynamic optimality. I'm being a little vague here because they don't resolve the DO conjecture: but they do strengthen some bounds and give some new insights that appear to come from the geometric formulation.

Improve this answer
$\endgroup$
11
$\begingroup$

I dont think there are any examples of such things. Except for linear programming, semi-definite programming, complex numbers, large fractions of machine learning, etc. The real question is http://www.youtube.com/watch?v=ExWfh6sGyso.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ any answer involving Monty Python deserves extra points :) $\endgroup$
    – Suresh Venkat
    May 9, 2011 at 19:22
9
$\begingroup$

There was a nice paper at POPL last year, EigenCFA: Accelerating flow analysis with GPUs, which represented lambda-terms as matrices and then used GPUs to rapidly perform dataflow analysis on them.

The paper didn't point this out explicitly, but what they were basically doing was exploiting the categorical structure of vector spaces to represent trees. That is, in ordinary set theory, a tree (of some fixed height) is a nested disjoint union of cartesian products.

However, vector spaces also have direct products and sums, so you can represent a tree as an element of a suitable vector space, as well. Moreover, direct products and direct sums coincide for vector spaces -- i.e., they have the same representation. This opens the door to parallel implementations: since the physical representations are the same, a lot of branching and pointer-chasing can be eliminated.

It also explains why dataflow analysis is cubic-time: it's computing eigenvectors!

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have any other example where this tree to vector spaces trick are used? EigenCFA paper requires too many background to understand. $\endgroup$
    – Chao Xu
    Aug 18, 2014 at 10:05
  • $\begingroup$ If I understand correctly, the tree/vector relation is just converting the tree to vector by listing the labels of the preorder traversal of the tree? $\endgroup$
    – Chao Xu
    Aug 18, 2014 at 10:37
8
$\begingroup$

In networking, routers use TCAMs (ternary content-addressable memories -- in other words, content addressable memory with a don't care bit) to classify traffic. Entries in a TCAM are often multidimensional prefix-match rules: for instance, (101*, 11*, 0*) matches any packet where the first header field starts with 101 and the second header field starts with 11 (and etc.) If a packet doesn't match the first rule, it goes on to the second, and so on until a matching rule is found.

The geometric interpretation is that rules on packets with $d$ header fields can be mapped to hyperplanes in $R^{d+1}$. The $d+1$th dimension is the priority of the rule. A packet is a line in $R^{d+1}$, where the first $d$ dimensions are fixed according to the packet's headers, and the $d+1$th dimension may vary. Packet matching is then an optimization problem: we want to find the hyperplane (rule) with the maximum priority dimension that is intersected by the line (packet).

For networking people, this interpretation is useful for understanding what a specific set of rules does. For theorists, there are other interesting uses. According to Algorithms for Packet Classification by Gupta and McKeown, the geometric interpretation allowed us to quickly establish lower and upper bounds for the problem of packet classification. I know work on TCAM rule minimization (finding the smallest number of rules that preserves semantics) has also benefited from a geometric approach. There are tons of references I could give for this, but the one that may be of the most use to you is Applegate, et al.'s SODA 2007 paper Compressing rectilinear pictures and minimizing access control lists. They prove that minimizing a more general variant of the prefix-matching rules above is NP-hard, and connect it (again) to pretty pictures of rectangles to solve the problem!

Improve this answer
$\endgroup$
8
$\begingroup$

I'm surprised nobody has said the Euclidean Algorithm for finding the greatest common factor between two numbers. You can deal with the problem by drawing an a x b rectangle, then subdivide the rectangle by the square created by the smallest side, repeat for the leftover rectangle, keep repeating for leftover rectangles until you find a square that can evenly divide a remaining rectangle (see animated gif on the Euclidean Algorithm page).

Pretty elegant way of trying to figure out how the thing works, IMO.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I think Euclid would argue that numbers do not qualify as "completely non-geometric"! $\endgroup$
    – Jeffε
    May 12, 2011 at 4:14
7
$\begingroup$

Probably there are too, too many examples to list, but one classical example (it is highlighted by Aigner and Ziegler as a "Proof from the Book") is the use by Lovász of a geometric representation to solve a problem in Shannon capacity. Though the proof was published in 1979 and solved an open question from 1956, this remains state-of-the-art.

Improve this answer
$\endgroup$
6
$\begingroup$

Relation of error correction codes with lattices, sphere packing etc. (e.g., Conway and Sloane book). Yet the relation is so strong, that it is not quite clear, if I should call error correction codes “completely not geometric” after that ...

Improve this answer
$\endgroup$
4
$\begingroup$

Lattice reduction techniques, such as LLL or PSLQ, are highly geometric and solve problems of pure number theory, such as linear Diophantine approximation and integer relation detection.

LLL was used to provide a polynomial time algorithm to factor (univariate) polynomials over $\mathbb{Z}$ whose co-efficients are drawn from $\mathbb{Z}$.

Improve this answer
$\endgroup$
3
$\begingroup$

Gerard Salton came up with this idea of using the cosine of the angle between vectors (cosine similarity) for information retrieval systems. This was used to compute term frequency–inverse document frequency. I consider this to be the predecessor of modern day search engines. See also Vector space model.

Improve this answer
$\endgroup$
1
$\begingroup$

The Necklace splitting problem is a very nice example. Its statement is purely combinatorial: assume that you have an open necklace with beads of $k$ different colours, and the number of beads of each colour is even. The necklace should be cut in several places in such a way that the pieces can be partitioned into two sets having exactly half of the beads of each colour. It's always enough to make only $k$ cuts. To prove it, put the necklace on the moment curve and use a variant of Ham Sandwich Theorem (see a nice book "Using the Borsuk–Ulam Theorem" by Jiří Matoušek).

Of course, the proof is more topological than geometrical, but in low dimension it has a clear geometrical picture. To the best of my knowledge, no purely combinatorial proof (i.e. a proof that you can explain to a person that refuses to hear anything about topology) exists.

Improve this answer
$\endgroup$
0
$\begingroup$

The role of space-filling curves in databases and optimization: http://people.csail.mit.edu/jaffer/Geometry/MDSFC

Improve this answer
$\endgroup$
-2
$\begingroup$

There exist computational geometry techniques to solve linear programming. Computational geometry: algorithms and applications has a nice and simple chapter about that.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ But linear programming — "Find the lowest point in this polyhedron" — is explicitly geometric. $\endgroup$
    – Jeffε
    May 12, 2011 at 4:15
-2
$\begingroup$

Support vector machine in machine learning probably qualifies.

Improve this answer
$\endgroup$
-3
$\begingroup$

A Definite Integral of a function can be represented as the signed area of the region bounded by its graph.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Correct, except that "can be represented as" should be spelled "is". $\endgroup$
    – Jeffε
    May 14, 2011 at 5:03

Your Answer

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

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