A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems

Determining the cells of an arrangement of hyperplanes is a classical problem in combinatorial geometry. In this paper we present an efficient recursive procedure to solve it.In fact, by considering a connection between the latter problem and optimality conditions of unconstrained quadratic optimization problems in the following form: (QP)min{xtQx∣x∈{−1,1}n}, with Q∈Rn×nQ∈Rn×n, we can show the proposed algorithm solves problems of the form (QP)(QP) in polynomial time when the rank of the matrix QQ is fixed and the number of its positive diagonal entries is O(log(n))O(log(n)).