Distribution-sensitive algorithms

Abstract

We investigate a new paradigm of algorithm design for geometric problems that can be termed distribution-sensitive. Our notion of distribution is more combinatorial in nature than spatial. We illustrate this on problems like planar-hulls and 2D-maxima where some of the previously known output-sensitive algorithms are recast in this setting. In a number of cases, the distribution-sensitive analysis yields superior results for the above problems. Moreover these bounds are shown to be tight for a certain class of algorithms. Our approach owes its spirit to the results known for sorting multisets and we exploit this relationship further to derive fast and efficient parallel algorithms for sorting multisets along with the geometric problems.