NP-Hardness of the Problem of Optimal Box Positioning

Alexei V. Galatenko, Stepan A. Nersisyan and Dmitriy N. Zhuk
Additional contact information
Alexei V. Galatenko: Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia
Stepan A. Nersisyan: Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia
Dmitriy N. Zhuk: Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia

Mathematics, 2019, vol. 7, issue 8, 1-6

Abstract: We consider the problem of finding a position of a d -dimensional box with given edge lengths that maximizes the number of enclosed points of the given finite set P ⊂ R d , i.e., the problem of optimal box positioning. We prove that while this problem is polynomial for fixed values of d , it is NP-hard in the general case. The proof is based on a polynomial reduction technique applied to the considered problem and the 3-CNF satisfiability problem.

Keywords: optimal box positioning; NP-hardness; computational geometry (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/8/711/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/8/711/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:8:p:711-:d:255294

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().