Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems

Klein, Rolf ; Levcopoulos, Christos LU orcid and Lingas, Andrzej LU (2018) In Algorithms 11(4).
Abstract
Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P∖R, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we... (More)
Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P∖R, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Algorithms
volume
11
issue
4
article number
45
publisher
MDPI AG
external identifiers
  • scopus:85069868840
ISSN
1999-4893
DOI
10.3390/a11040045
language
English
LU publication?
yes
id
a8bb4fed-75be-4c72-8695-f8942448194a
date added to LUP
2018-04-12 17:54:47
date last changed
2021-09-29 02:55:23
@article{a8bb4fed-75be-4c72-8695-f8942448194a,
  abstract     = {Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P∖R, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.},
  author       = {Klein, Rolf and Levcopoulos, Christos and Lingas, Andrzej},
  issn         = {1999-4893},
  language     = {eng},
  month        = {04},
  number       = {4},
  publisher    = {MDPI AG},
  series       = {Algorithms},
  title        = {Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems},
  url          = {http://dx.doi.org/10.3390/a11040045},
  doi          = {10.3390/a11040045},
  volume       = {11},
  year         = {2018},
}