Optimal space coverage with white convex polygons

Shayan Ehsani (), MohammadAmin Fazli (), Mohammad Ghodsi () and MohammadAli Safari ()
Additional contact information
Shayan Ehsani: Stanford University
MohammadAmin Fazli: Sharif University of Technology
Mohammad Ghodsi: Sharif University of Technology
MohammadAli Safari: Sharif University of Technology

Journal of Combinatorial Optimization, 2016, vol. 32, issue 2, No 2, 353 pages

Abstract: Abstract Assume that we are given a set of points some of which are black and the rest are white. The goal is to find a set of convex polygons with maximum total area that cover all white points and exclude all black points. We study the problem on three different settings (based on overlapping between different convex polygons): (1) In case convex polygons are permitted to have common area, we present a polynomial algorithm. (2) In case convex polygons are not allowed to have common area but are allowed to have common vertices, we prove the NP-hardness of the problem and propose an algorithm whose output is at least $$\left( \frac{OPT}{log(2n/OPT) + 2log(n)}\right) ^{1/4}$$ O P T l o g ( 2 n / O P T ) + 2 l o g ( n ) 1 / 4 . (3) Finally, in case convex polygons are not allowed to have common area or common vertices, also we prove the NP-hardness of the problem and propose an algorithm whose output is at least $$\frac{3\sqrt{3}}{4.\pi }\left( \frac{OPT}{log(2n/OPT) + 2log(n)}\right) ^{1/4}$$ 3 3 4 . π O P T l o g ( 2 n / O P T ) + 2 l o g ( n ) 1 / 4 .

Keywords: White convex polygon; Convex covering; NP-hardness; Algorithm (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9822-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:32:y:2016:i:2:d:10.1007_s10878-014-9822-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9822-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().