User Vinayak Pathak

28 votes

17 answers

3k views

Examples where insight from geometry was useful for solving something completely non-geometric

asked May 9, 2011 at 3:38

21 votes

2 answers

1k views

Element distinctness in O(n) time?

asked Nov 14, 2012 at 19:26

17 votes

1 answer

816 views

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

asked Feb 15, 2013 at 21:18

15 votes

1 answer

806 views

Is the lower bound proof in this paper correct?

asked Aug 31, 2010 at 20:42

15 votes

1 answer

540 views

Drawing graphs with few "sharp" vertices?

asked May 1, 2012 at 19:56

13 votes

1 answer

860 views

Largest common subgraph of two maximal planar graphs

asked Apr 14, 2011 at 22:51

13 votes

1 answer

571 views

Given a graph, decide if its edge connectivity is at least n/2 or not

asked Sep 5, 2011 at 15:40

12 votes

1 answer

556 views

Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

asked Oct 11, 2011 at 4:12

10 votes

1 answer

252 views

Places where the order of points along a simple polygon passing through them is useful

asked May 9, 2011 at 14:34

5 votes

1 answer

321 views

Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

asked Mar 9, 2011 at 0:38

Stack Exchange Network

10 Questions

Examples where insight from geometry was useful for solving something completely non-geometric

Element distinctness in O(n) time?

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

Is the lower bound proof in this paper correct?

Drawing graphs with few "sharp" vertices?

Largest common subgraph of two maximal planar graphs

Given a graph, decide if its edge connectivity is at least n/2 or not

Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

Places where the order of points along a simple polygon passing through them is useful

Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?