Geometric Optimization and Computational Complexity

Other Titles
Our purpose here is to study problems involving geometric optimization, namely, questions of the type: Is there at least a minimum or at most a maximum number of certain geometric figures, that are within certain distances of other figures (objects). We are also concerned with the optimization of the size of these geometric figures. These problems arise as geometric reductions from various classes of location-allocation optimization problems and are inherently not pure combinatorial. Our primary aim, then, is to discover techniques of dealing with such geometric optimization problems, while adapting to these problems the older combinatorial design and analysis methods. The task of classifying problems accurately in the polynomial hierarchy is one of increasing importance. To solve an optimization problem deterministically it seems that one must solve both an $NP$ and a $Co-NP$ problem. The significance of the classes $NP$ and $Co-NP$ are that none of the problems they include is known to have a polynomial time solution. We show that if $NP \neq Co-NP$ then there are interesting natural geometric optimization problems (location-allocation problems under minsum) in $\Delta^{P}_{2}$ that are in neither $NP$ nor $Co-NP$. Hence, all these problems are shown to belong properly to $\Delta^{P}_{2}$, the second level of the polynomial hierarchy. We also show that if $NP \neq Co-NP$ then there are again some interesting geometric optimization problems (location-allocation problems under minmaz) properly in $\Delta^{P}_{2}$ and furthermore they are complete for a class $D^{P}$ (which is contained in $\Delta^{P}_{2}$ and contains $NP \bigcup Co-NP$). Also considered are the above geometric location-allocation optimization problems for the case when the allocation is predetermined. Both efficient algorithms and worst-case lower bounds are derived. Necessary conditions for the existence of mazima and minima in optimization problems are generally tied to the question of solvability of an equation or a system of equations. In calculus these equations are algebraic. By generating the minimal polynomial whose root over the field of rational numbers is the solution of the geometric optimization problem on the real (Euclidean) plane, we are able to prove the non-solvability of certain geometric optimization problems by radicals. The algebraic degree of the optimizing solution, which is the degree of the irreducible minimal polynomial for the problem, correlates with the inherent difficulty of constructing the solution and provides an algebraic complexity measure for these geometric optimization problems.
Journal / Series
Volume & Issue
Date Issued
Cornell University
computer science; technical report
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
technical report
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record