## On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension


Jiri Matousek (joint work with Bernard Chazelle)
Department of Computer Science
Charles University, CSFR
Report B 92-18
September 92

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-18.ps.gz

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic one. The constant of proportionality is $d^{O(d)}$, which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of $n$ halfspaces) in linear time.\\[1mm] {\bf Keywords:} Computational complexity, computational geometry, geometric optimization problem, randomized algorithm, derandomization