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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic

149 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)
Plaats van productie	Zürich
Uitgeverij	ETH Zürich
Pagina's	103-106
Status	Gepubliceerd - 2011

Toegang tot document

Metis253579Definitieve gepubliceerde versie, 867 KB

Citeer dit

@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. et al.
Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011). Zürich: ETH Zürich, 2011. blz. 103-106.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit