Skip to Main content Skip to Navigation
Conference papers

Algorithms for Deciding Membership in Polytopes of General Dimension

Abstract : We study the fundamental problem of polytope membership aiming at large convex polytopes, i.e. in high dimension and with many facets, given as an intersection of halfspaces. Standard data-structures as well as brute force methods cannot scale, due to the curse of dimen- sionality. We design an efficient algorithm, by reduction to the approx- imate Nearest Neighbor (ANN) problem based on the construction of a Voronoi diagram with the polytope being one bounded cell. We thus trade exactness for efficiency so as to obtain complexity bounds polyno- mial in the dimension, by exploiting recent progress in the complexity of ANN search. We employ this algorithm to present a novel boundary data structure based on a Newton-like iterative intersection procedure. We implement our algorithms and compare with brute-force approaches to show that they scale very well as the dimension and number of facets grow larger.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Ioannis Emiris Connect in order to contact the contributor
Submitted on : Friday, October 19, 2018 - 9:50:04 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Sunday, January 20, 2019 - 12:47:24 PM


Files produced by the author(s)


  • HAL Id : hal-01897486, version 1
  • ARXIV : 1804.11295



Evangelos Anagnostopoulos, Ioannis Z. Emiris, Vissarion Fisikopoulos. Algorithms for Deciding Membership in Polytopes of General Dimension. Combinatorial Optimization - 5th International Symposium, ISCO 2018, Apr 2018, Marrakesh, Morocco. ⟨hal-01897486⟩



Record views


Files downloads