Maximum Weight Convex Polytope

2022/07/26 by Mohammad Ali Abam, Abam, Mohammad Ali, Ali Mohammad Lavasani +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2207.12915

openalex publication_date 2022/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the maximum weight convex polytope problem, in which the goal is to find a convex polytope maximizing the total weight of enclosed points. Prior to this work, the only known result for this problem was an O(n³) algorithm for the case of 2 dimensions due to Bautista et al. We show that the problem becomes NP-hard to solve exactly in 3 dimensions, and NP-hard to approximate within n^1/2-ε for any ε> 0 in 4 or more dimensions. %\polyAPX-complete in 4 dimensions even with binary weights. We also give a new algorithm for 2 dimensions, albeit with the same O(n³) running time complexity as that of the algorithm of Bautsita et al.

Related

• Finding Largest Rectangles in Convex Polygons
• A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes
• Tight Hardness Results for Maximum Weight Rectangles
• Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter
• Maximum volume polytopes inscribed in the unit sphere