Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness

David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1

We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…