Optimal space coverage with white convex polygons

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 diffe...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2016-08, Vol.32 (2), p.341-353
Main Authors: Ehsani, Shayan, Fazli, MohammadAmin, Ghodsi, Mohammad, Safari, MohammadAli
Format: Article
Language:English
Subjects:
Combinatorics
Convex and Discrete Geometry
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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 3 3 4 . π O P T l o g ( 2 n / O P T ) + 2 l o g ( n ) 1 / 4 .
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-014-9822-1