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 CoNP problem. The significance of the classes NP and CoNP are that none of the problems they include is known to have a polynomial time solution. We show that if NPCoNP then there are interesting natural geometric optimization problems (location-allocation problems under minsum) in Δ2P that are in neither NP nor CoNP. Hence, all these problems are shown to belong properly to Δ2P, the second level of the polynomial hierarchy. We also show that if NPCoNP then there are again some interesting geometric optimization problems (location-allocation problems under minmaz) properly in Δ2P and furthermore they are complete for a class DP (which is contained in Δ2P and contains NPCoNP). 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