Hacker News Reader

One day I will understand why seemingly half of all CS papers seem to be concerned with convex hulls and Voronoi decomposition. What is so fascinating about these two topics as to warrant hundreds, if not thousands of papers? I've never heard of anyone using them anywhere ever for any purpose in industry, yet these topics are a focus of concentrated intellectual study as if they were the cure for cancer.

View on HN

An entire industry – geospatial – and a variety of related industries depend on high-performance CH, Voronoi, and line simplification algorithms, among others. Not to mention their importance in medical imaging applications, tomography (so, in a sense, they directly contribute to healthcare improvements). This should be self-evident, but I can provide further direct evidence if need be; I’ve implemented QuickHull, Visvalingam-Whyatt etc from the papers, and the resulting libraries see enthusiastic use in a variety of sometimes surprising fields. They get lots of attention because the problem domain is well-understood and often resistant to low-hanging optimisation efforts (computational geometry algorithms tend to be difficult to optimise)

Reply on news.ycombinator.com