2
$\begingroup$

Planar Convex Hull is a problem where you have $N$ points in a Cartesian plane, and you want to find the smallest convex polygon that encloses the points. QuickHull seems to be the best available algorithm for this, and it finds the hull in $O(N \log h)$ where $h$ is the size of the output.

Interestingly, Michael Shamos points out in his 78 PhD thesis that there's a much simpler physical algorithm (call it the Carpenter's algorithm) which solves Convex Hull in time complexity $O(N)$. Just take a wooden board, hammer a nail in for each point of the set, and wrap a rubber band around the points to determine the convex hull.

I'm totally bewildered by this apparent discrepancy. Why haven't we developed a computer program to solve Convex Hull in $O(N)$ time?

$\endgroup$
4
  • $\begingroup$ I'm going to claim that this "physical" algorithm runs in time $\Omega(n \log n)$. How, exactly, are you counting the "pegs" that are part of the hull or not? Imagine $n$ pegs that are almost perfectly spread on a circle, but each peg is some subatomic distance from the perfect hull (supposing we ignore Heisenberg here). $\endgroup$
    – Pål GD
    Dec 8, 2022 at 9:16
  • $\begingroup$ @PålGD: I don't get your argument. Counting the pegs would take at worse $n$ operations; and if not, why $n\log n$ ?? $\endgroup$
    – user16034
    Dec 8, 2022 at 10:49
  • $\begingroup$ How do you measure if a peg is part of the hull or not? $\endgroup$
    – Pål GD
    Dec 8, 2022 at 11:07
  • $\begingroup$ In fact, we cannot acknowledge Shamo's statement. Indeed you do hammer $n$ nails, but what is the cost of wrapping a rubber band ? $\endgroup$
    – user16034
    Dec 8, 2022 at 13:28

2 Answers 2

3
$\begingroup$

Carpenter's algorithm isn't implementable in a computer and makes assumptions that are not realistic in practice, such as that nature works with infinite-precision arithmetic and that you can choose the location of the nail with infinite precision in constant time and that the rubber band will find the global optimum in constant time and that you can measure in constant time whether a particular nail is touching the rubber band. As such Carpenter's algorithm is basically a cute idea that is most likely a distraction for purposes of understanding how fast you can solve very large problems in practice.

See also NP-complete Problems and Physical Reality, Scott Aaronson, SIGACT News, vol 36 no 1, March 2005.

$\endgroup$
2
$\begingroup$

Nail all $n$ points in time $O(n)$. Then sweep a vertical taut rope from far left until you hit the leftmost nail. Next you have two options:

  • rotate the two ends until you hit other nails, and continue until you complete the hull "by wrapping". This takes $O(h)$ sweep operations, as you wind every nail once and unwind at most once.

  • wind the rope to the next two nails (up and down) in angular order, and as long as the rope forms a reflex angle, unwind from the angle vertex. This takes at most $O(n)$ operations.

What we are missing is the operation "sweep to the next nail" in constant time. The best we have is a sweep in time $O(n)$, or a sweep in constant time $O(1)$ after preprocessing by sorting, $O(n\log n)$.


Should I add that none of this makes sense as long as you have not defined a real cost function ?

$\endgroup$

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.