Geometric optimization andD P -completeness

In this paper we show a number of natural geometric optimization problems in the plane to becomplete for a classD ^P . The classD ^p contains both NP and Co-NP and is contained in ₂ ^P =P ^NP. Completeness inD ^p is exhibited under many-one and positive reductions. Further anOptP(O(logn)) result is also obtained for some of these optimization problems.Work on this paper by the first author was supported in part by NSF Grant No. MIP 85-21356 and ARO Contract No. DAAG29-85-C-0018 under Cornell/MSI. Work by the second author was supported in part by NSF Grant No. DCR 86-06366 at Ohio State and ONR Grant No. N00014-k-0045 at Harvard.On leave from Ohio State University.