Certain geometric optimization problems, for example finding the
smallest enclosing ellipse of a set of points, can be solved in
linear time by simple randomized (or complicated deterministic)
combinatorial algorithms. In practice, these algorithms are enhanced
or replaced with heuristic variants that are faster but do not come
with a theoretical runtime guarantee.
In this paper, we introduce a new speed-up heuristic that can easily
be integrated into the known linear-time algorithms, without
decreasing their worst-case performance. The heuristic can actually
be defined for every problem in the well-known abstract class of
LP-type problems; its effectiveness in practice depends on whether
and how fast the heuristic can be implemented for the specific
problem at hand, and on whether the input distribution is favorable.
We provide test results showing that for two concrete
problems, the new heuristic may lead to significant speedups compared
to state-of-the-art implementations that are available in the
Computational Geometry Algorithms Library CGAL.