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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

23 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 languageEnglish
Title of host publicationAbstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)
Place of PublicationZürich
PublisherETH Zürich
Pages103-106
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'A 3-approximation algorithm for computing partitions with minimum stabbing number of rectilinear simple polygons'. Together they form a unique fingerprint.

Cite this