<p>A few more examples:</p>

<p>Sleator, Thurston and Tarjan used a geometric representation of trees as partitions of polygons, and hyperbolic geometry, to prove <a href="http://portal.acm.org/citation.cfm?id=12143">lower bounds for binary tree rotation</a>. (Also, I believe the <em>history</em> of a dynamic binary search tree can be represented as a tetrahedralization.)</p>

<p>The reduction of <a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">least common ancestor to range minimum queries</a>, due to Berkman and Vishkin, relates a data structures problem on trees to an arguably-geometric problem. (and thanks for the article David)</p>

<p>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.</p>

<p>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).</p>

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

<p>[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.</p>

<p>[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):</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.5749">algebraic topology applied to lower bounds for distributed computing</a></p>

<p><a href="http://en.wikipedia.org/wiki/Effective_dimension">incorporating computability into Hausdorff dimension</a></p>

<p><a href="http://www.ams.org/jams/2010-23-03/S0894-0347-09-00658-4/S0894-0347-09-00658-4.pdf">defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"</a></p>

CC BY-SA 3.0
2011-05-10T19:23:04.857Z
Nikhil's paper is a very interesting example, that I somehow forgot about.
Sasho Nikolov
CC BY-SA 3.0
2011-05-10T20:17:51.090Z
Welcome to cstheory, Ken :)
Suresh Venkat
CC BY-SA 3.0
2011-05-15T19:16:53.387Z
Nobody seems to mention the planar separator theorem... Which turns out to be an easy consequence of Koebe theorem.
Sariel Har-Peled
CC BY-SA 3.0
2011-05-16T03:09:56.720Z
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".
Chandra Chekuri
CC BY-SA 3.0
2011-06-03T21:45:50.930Z
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).
didest
CC BY-SA 3.0
2011-05-10T18:06:23.207Z
2011-05-11T17:12:11.230Z
2011-05-11T17:12:11.230Z
Ken Clarkson
<p>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 <a href="http://dl.acm.org/citation.cfm?doid=800057.808694" rel="nofollow">Saks and Kahn</a> 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 <a href="http://www.sciencedirect.com/science/article/pii/S002200008571077X" rel="nofollow">first polynomial time algorithm</a> (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.</p>

CC BY-SA 3.0
2011-05-09T04:26:27.533Z
2014-03-18T00:49:33.283Z
2014-03-18T00:49:33.283Z
Sasho Nikolov
<p>There's a relatively recent paper <a href="http://people.csail.mit.edu/mip/papers/arboral/paper.pdf">by Demaine et al</a> 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. </p>

CC BY-SA 3.0
2011-05-09T04:26:19.327Z
2011-05-09T04:26:19.327Z
Suresh Venkat
<p>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 <a href="http://www.youtube.com/watch?v=ExWfh6sGyso">http://www.youtube.com/watch?v=ExWfh6sGyso</a>.</p>

CC BY-SA 3.0
2011-05-09T19:22:48.563Z
any answer involving Monty Python deserves extra points :)
Suresh Venkat
CC BY-SA 3.0
2011-05-09T06:04:35.633Z
2011-05-09T06:04:35.633Z
Sariel Har-Peled
<p>Of course a <em>much</em> 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 <a href="http://link.springer.com/article/10.1007/BF01200757#page-1" rel="nofollow">the realization that it could be approximated by finding a good embedding of a general metric into an $\ell_1$-normed space</a>. </p>

CC BY-SA 3.0
2014-03-17T23:56:18.023Z
Could you please cite the paper?
user
CC BY-SA 3.0
2014-03-18T00:10:49.623Z
@user here you go.
Suresh Venkat
CC BY-SA 3.0
2011-05-09T04:28:07.503Z
2014-03-18T00:10:37.700Z
2014-03-18T00:10:37.700Z
Suresh Venkat
<p>There was a nice paper at POPL last year, <a href="http://matt.might.net/papers/prabhu2011eigencfa.pdf">EigenCFA: Accelerating flow analysis with GPUs</a>, which represented lambda-terms as matrices and then used GPUs to rapidly perform dataflow analysis on them. </p>

<p>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. </p>

<p>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. </p>

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

CC BY-SA 3.0
2014-08-18T10:05:58.080Z
Do you have any other example where this tree to vector spaces trick are used? EigenCFA paper requires too many background to understand.
Chao Xu
CC BY-SA 3.0
2014-08-18T10:37:18.930Z
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?
Chao Xu
CC BY-SA 3.0
2011-05-09T08:49:27.897Z
2011-05-09T08:49:27.897Z
Neel Krishnaswami
<p>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.</p>

<p>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).</p>

<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.861&amp;rep=rep1&amp;type=pdf&amp;rct=j&amp;q=algorithms%20for%20packet%20classification&amp;ei=tnzHTfjEGYfe0QG97KmBCA&amp;usg=AFQjCNFwaMDw-_NWFxeZALn4RO_7Vmx1xQ">Algorithms for Packet Classification</a> 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 <a href="http://www.cs.cornell.edu/~katrina/papers/acl.pdf">Compressing rectilinear pictures and minimizing access control lists</a>. 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!</p>

CC BY-SA 3.0
2011-05-09T05:43:43.503Z
2011-05-09T05:43:43.503Z
Christopher Monsanto
<p>I'm surprised nobody has said the <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm">Euclidean Algorithm</a> 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).</p>

<p>Pretty elegant way of trying to figure out how the thing works, IMO.</p>

CC BY-SA 3.0
2011-05-12T04:14:38.840Z
I think Euclid would argue that numbers do not qualify as "completely non-geometric"!
Jeffε
CC BY-SA 3.0
2011-05-09T14:02:13.697Z
2011-05-09T14:02:13.697Z
Doug T.
<p>Probably there are too, too many examples to list, but one classical example (it is highlighted by Aigner and Ziegler as a "<a href="http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK">Proof from the Book</a>") 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.</p>

CC BY-SA 3.0
2011-05-09T07:42:22.303Z
2011-05-09T07:42:22.303Z
RJK
<p>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 ...</p>

CC BY-SA 3.0
2011-05-09T20:17:45.400Z
2011-05-09T20:17:45.400Z
Alex 'qubeat'
<p>Lattice reduction techniques, such as <a href="http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" rel="nofollow">LLL</a> or <a href="http://mathworld.wolfram.com/PSLQAlgorithm.html" rel="nofollow">PSLQ</a>, are highly geometric and solve problems of pure number theory, such as linear Diophantine approximation and integer relation detection.</p>

<p><a href="http://www.math.elte.hu/~lovasz/scans/lll.pdf" rel="nofollow">LLL</a>  was used to provide a polynomial time algorithm to factor (univariate) polynomials over $\mathbb{Z}$ whose co-efficients are drawn from $\mathbb{Z}$.</p>

CC BY-SA 3.0
2011-05-09T08:01:46.873Z
2011-05-09T08:01:46.873Z
user834
<p><a href="http://en.wikipedia.org/wiki/Gerard_Salton" rel="nofollow">Gerard Salton</a> 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 <a href="http://en.wikipedia.org/wiki/Tf-idf" rel="nofollow">term frequency–inverse document frequency.</a>  I consider this to be the predecessor of modern day search engines. See also <a href="http://en.wikipedia.org/wiki/Vector_space_model" rel="nofollow">Vector space model.</a></p>

CC BY-SA 3.0
2011-05-09T14:07:32.933Z
2011-05-09T14:07:32.933Z
jftuga
<p>The <a href="https://en.wikipedia.org/wiki/Necklace_splitting_problem" rel="nofollow noreferrer">Necklace splitting problem</a> 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).</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-10T02:42:03.663Z
2017-02-10T02:59:44.087Z
2017-02-10T02:59:44.087Z
Andrew Ryzhikov
<p>The role of space-filling curves in databases and optimization:
<a href="http://people.csail.mit.edu/jaffer/Geometry/MDSFC" rel="nofollow noreferrer">http://people.csail.mit.edu/jaffer/Geometry/MDSFC</a></p>

CC BY-SA 3.0
2017-02-10T11:59:32.940Z
2017-02-10T11:59:32.940Z
Aryeh
<p>There exist computational geometry techniques to solve linear programming.
<a href="http://rads.stackoverflow.com/amzn/click/3642096816" rel="nofollow">Computational geometry: algorithms and applications</a> has a nice and simple chapter about that. </p>

CC BY-SA 3.0
2011-05-12T04:15:58.213Z
But linear programming — "Find the lowest point in this polyhedron" — is explicitly geometric.
Jeffε
CC BY-SA 3.0
2011-05-09T18:26:57.467Z
2011-05-09T18:26:57.467Z
Luca Zanetti
<p>Support vector machine in machine learning probably qualifies.</p>

CC BY-SA 3.0
2011-05-09T05:49:46.613Z
2017-02-04T15:26:28.613Z
2017-02-04T15:26:28.613Z
mirror2image
<p>A <a href="http://en.wikipedia.org/wiki/Integral" rel="nofollow">Definite Integral</a> of a function can be represented as the signed area of the region bounded by its graph.</p>

CC BY-SA 3.0
2011-05-14T05:03:36.523Z
Correct, except that "can be represented as" should be spelled "is".
Jeffε
CC BY-SA 3.0
2011-05-12T11:51:48.297Z
2011-05-12T11:51:48.297Z
George Polevoy
<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-09T05:23:53.177Z
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 :)
Suresh Venkat
CC BY-SA 3.0
2011-05-09T10:46:36.427Z
plenty of such examples can be found in the proofs without words section of American Mathematical Monthly
jimjim
<big-list><cg.comp-geom><big-picture>
Examples where insight from geometry was useful for solving something completely non-geometric
Vinayak Pathak
# Examples where insight from geometry was useful for solving something completely non-geometric

(Asked by: username_0 on 2011-05-09)

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.

**Tags:** big-list, cg.comp-geom, big-picture
> **Comments:**
> **username_1**: 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 :)  
> **username_2**: plenty of such examples can be found in the proofs without words section of American Mathematical Monthly  

---

## 17 answers

### Answer by username_3 on 2011-05-10. Score: 24

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](http://portal.acm.org/citation.cfm?id=12143). (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](http://en.wikipedia.org/wiki/Lowest_common_ancestor), 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.5749)

[incorporating computability into Hausdorff dimension](http://en.wikipedia.org/wiki/Effective_dimension)

[defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"](http://www.ams.org/jams/2010-23-03/S0894-0347-09-00658-4/S0894-0347-09-00658-4.pdf)

> **Comments:**
> **username_4**: Nikhil's paper is a very interesting example, that I somehow forgot about.  
> **username_1**: Welcome to cstheory, Ken :)  
> **username_5**: Nobody seems to mention the planar separator theorem... Which turns out to be an easy consequence of Koebe theorem.  
> **username_6**: 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".  
> **username_7**: 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).  

---

### Answer by username_1 on 2011-05-09. Score: 15

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](http://link.springer.com/article/10.1007/BF01200757#page-1).

> **Comments:**
> **username_8**: Could you please cite the paper?  
> **username_1**: @user here you go.  

---

### Answer by username_4 on 2011-05-09. Score: 12

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](http://dl.acm.org/citation.cfm?doid=800057.808694) 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](http://www.sciencedirect.com/science/article/pii/S002200008571077X) (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.


---

### Answer by username_1 on 2011-05-09. Score: 11

There's a relatively recent paper [by Demaine et al](http://people.csail.mit.edu/mip/papers/arboral/paper.pdf) 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.


---

### Answer by username_5 on 2011-05-09. Score: 11

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

> **Comments:**
> **username_1**: any answer involving Monty Python deserves extra points :)  

---

### Answer by username_9 on 2011-05-09. Score: 9

There was a nice paper at POPL last year, [EigenCFA: Accelerating flow analysis with GPUs](http://matt.might.net/papers/prabhu2011eigencfa.pdf), 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!

> **Comments:**
> **username_10**: Do you have any other example where this tree to vector spaces trick are used? EigenCFA paper requires too many background to understand.  
> **username_10**: 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?  

---

### Answer by username_11 on 2011-05-09. Score: 8

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.861&rep=rep1&type=pdf&rct=j&q=algorithms%20for%20packet%20classification&ei=tnzHTfjEGYfe0QG97KmBCA&usg=AFQjCNFwaMDw-_NWFxeZALn4RO_7Vmx1xQ) 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](http://www.cs.cornell.edu/~katrina/papers/acl.pdf). 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!


---

### Answer by username_12 on 2011-05-09. Score: 8

I'm surprised nobody has said the [Euclidean Algorithm](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_13**: I think Euclid would argue that numbers do not qualify as "completely non-geometric"!  

---

### Answer by username_14 on 2011-05-09. Score: 7

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](http://en.wikipedia.org/wiki/Proofs_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.


---

### Answer by username_15 on 2011-05-09. Score: 6

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


---

### Answer by username_16 on 2011-05-09. Score: 4

Lattice reduction techniques, such as [LLL](http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) or [PSLQ](http://mathworld.wolfram.com/PSLQAlgorithm.html), are highly geometric and solve problems of pure number theory, such as linear Diophantine approximation and integer relation detection.

[LLL](http://www.math.elte.hu/~lovasz/scans/lll.pdf) was used to provide a polynomial time algorithm to factor (univariate) polynomials over $\mathbb{Z}$ whose co-efficients are drawn from $\mathbb{Z}$.


---

### Answer by username_17 on 2011-05-09. Score: 3

[Gerard Salton](http://en.wikipedia.org/wiki/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.](http://en.wikipedia.org/wiki/Tf-idf) I consider this to be the predecessor of modern day search engines. See also [Vector space model.](http://en.wikipedia.org/wiki/Vector_space_model)


---

### Answer by username_18 on 2017-02-10. Score: 1

The [Necklace splitting problem](https://en.wikipedia.org/wiki/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.


---

### Answer by username_19 on 2017-02-10. Score: 0

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


---

### Answer by username_20 on 2011-05-09. Score: -2

There exist computational geometry techniques to solve linear programming.
[Computational geometry: algorithms and applications](http://rads.stackoverflow.com/amzn/click/3642096816) has a nice and simple chapter about that.

> **Comments:**
> **username_13**: But linear programming — "Find the lowest point in this polyhedron" — is explicitly geometric.  

---

### Answer by username_21 on 2011-05-09. Score: -2

Support vector machine in machine learning probably qualifies.


---

### Answer by username_22 on 2011-05-12. Score: -3

A [Definite Integral](http://en.wikipedia.org/wiki/Integral) of a function can be represented as the signed area of the region bounded by its graph.

> **Comments:**
> **username_13**: Correct, except that "can be represented as" should be spelled "is".  

---

