A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons

M.A. Abam; B. Aronov; M.T. Berg, de; A. Khosravi Dehkordi

A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons

M.A. Abam, B. Aronov, M.T. Berg, de, A. Khosravi Dehkordi

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

28 Downloads (Pure)

Abstract

Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel segment inside P. We present a 3-approximation algorithm for fi??nding a partition with minimum stabbing number. It is based on an algorithm that ??finds an optimal partition for histograms.

Original language	English
Title of host publication	Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)
Place of Publication	Zürich
Publisher	ETH Zürich
Pages	103-106
Publication status	Published - 2011

Access to Document

Metis253579Final published version, 867 KB

Cite this

@inproceedings{e168ed9cd94840a9939fb972a513ecfd,

title = "A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons",

abstract = "Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel segment inside P. We present a 3-approximation algorithm for fi??nding a partition with minimum stabbing number. It is based on an algorithm that ??finds an optimal partition for histograms.",

author = "M.A. Abam and B. Aronov and {Berg, de}, M.T. and {Khosravi Dehkordi}, A.",

year = "2011",

language = "English",

pages = "103--106",

booktitle = "Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)",

publisher = "ETH Z{\"u}rich",

}

A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons. / Abam, M.A.; Aronov, B.; Berg, de, M.T.; Khosravi Dehkordi, A.

Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011). Zürich : ETH Zürich, 2011. p. 103-106.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons

AU - Abam, M.A.

AU - Aronov, B.

AU - Berg, de, M.T.

AU - Khosravi Dehkordi, A.

PY - 2011

Y1 - 2011

N2 - Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel segment inside P. We present a 3-approximation algorithm for fi??nding a partition with minimum stabbing number. It is based on an algorithm that ??finds an optimal partition for histograms.

AB - Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel segment inside P. We present a 3-approximation algorithm for fi??nding a partition with minimum stabbing number. It is based on an algorithm that ??finds an optimal partition for histograms.

M3 - Conference contribution

SP - 103

EP - 106

BT - Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)

PB - ETH Zürich

CY - Zürich

ER -

A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons

Abstract

Access to Document

Fingerprint

Cite this