Sariel Har-Peled
• Member for 11 years, 5 months
• Last seen this week
• Urbana, IL

I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where ...

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely ...

Set cover by half-spaces. Given a set of points in the plane, and a set of halfplanes computing the minimum number of halfplanes covering the point sets can be solved in polynomial time in the plane. ...

If I may quote Sarah Palin on this issue: "All of them". More seriously, I think most papers should not be read in the original. As time passes people figure out better way of understanding and ...

Apology. Never have casual conversations with people. Its rude. Also what Peter Shor said. I would also add that if you ask the question, then usually the right thing is to offer this person to be ...

Fixed point theorems are all over the place... But a pretty surprising example of geometry popping from nowhere is the effective comparison result. Here, given a partial order defined over a set of $... View answer Accepted answer 17 votes Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first: A point set$P$is in convex position if no point of$P$can be written as a convex combination of the ... View answer Accepted answer 17 votes First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number ... View answer 16 votes The books by Matousek & Chazelle on Discrepancy are excellent. Almost all the books by Matousek, in fact, are worth reading to some extent. Douglas West books on Graph Theory ([1] and [2]) are ... View answer 16 votes Computing the closest pair of points in the plane in linear time (especially because there is Omega(n log n) lower bound in the comparison model). The algorithm is originally due to Rabin, but there ... View answer Accepted answer 15 votes The lower bound is correct (2) - you can not do this better than$\Omega(n^2 \log n)$and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in ... View answer Accepted answer 15 votes Well, here is an first try silly answer... Take a plane through each face of of the rectangular boxes. This form a grid of size$O(n^3)$. It is not hard to compute for each such grid cell whether its ... View answer Accepted answer 14 votes Well, you can apply the planar separator theorem together with dynamic programming and get running time$2^{O(\sqrt{n})}$, where$n$is the number of vertices in the graph. The idea being that you try ... View answer 14 votes I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there ... View answer Accepted answer 12 votes As suggested by the other answer,$\Omega(\log n)$lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and ... View answer 12 votes The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the$L_\infty$metric) at least$1$from each ... View answer 11 votes There are two natural strategies: Put it on the arxiv, forget about publishing it somewhere else. I have several such writeups - people see them and cite them. Go to lower venue conferences. Don't ... View answer 11 votes For$n$points there are$O(n^3)$empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs). For ... View answer Accepted answer 11 votes The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the ... View answer Accepted answer 11 votes Here I am explaining how to get$O(n *\mathrm{polylog} n)$randomized running time. We need a sequence of observations: A witness of a value$v$is a pair of numbers$(a,b) \in A \times B$such that$...

Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO. One can get 1+eps approximation algorithm using sliding grids. It is natural to assume the problem is NP-Hard because ...

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

The answer is yes - the problem is still NP-Complete. for every set $S_i$ create a fake elements $e_i', e_i''$ and create a new sets $S_i' = S_i \cup \{ e_i'\}$ and $S_i'' =... View answer Accepted answer 10 votes The intersection graph of interior disjoint balls in$\mathbb{R}^d$, should have treewidth$O(n^{1-1/d})\$, if there is justice in the universe (let me think about it - yep - there is). The treewidth ...

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/...

If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets ...

Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest ...

jflap is pretty nice and can do this. See here: http://www.cs.duke.edu/csed/jflap/.