On rectilinear partitions with minimum stabbing number

M.T. Berg, de, A. Khosravi Dehkordi, S. Verdonschot, V. Weele, van der

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
10 Downloads (Pure)

Abstract

Let S be a set of n points in \Bbb RdUnknown control sequence '\Bbb', and let r be a parameter with 1¿=¿r¿=¿n. A rectilinear r-partition for S is a collection ¿(S) :¿=¿{(S 1,b 1),…,(S t ,b t )}, such that the sets S i form a partition of S, each b i is the bounding box of S i , and n/2r¿=¿|S i |¿=¿2n/r for all 1¿=¿i¿=¿t. The (rectilinear) stabbing number of ¿(S) is the maximum number of bounding boxes in ¿(S) that are intersected by an axis-parallel hyperplane h. We study the problem of finding an optimal rectilinear r-partition—a rectilinear partition with minimum stabbing number—for a given set S. We obtain the following results. • Computing an optimal partition is np-hard already in \Bbb R2Unknown control sequence '\Bbb'. • There are point sets such that any partition with disjoint bounding boxes has stabbing number O(r 1¿-¿1/d ), while the optimal partition has stabbing number 2. • An exact algorithm to compute optimal partitions, running in polynomial time if r is a constant, and a faster 2-approximation algorithm. • An experimental investigation of various heuristics for computing rectilinear r-partitions in \Bbb R2Unknown control sequence '\Bbb'.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures (12th International Workshop, WADS 2011, Brooklyn NY, USA, August 15-17, 2011. Proceedings)
EditorsF. Dehne, J. Iacono, F.R. Sack
Place of PublicationBerlin
PublisherSpringer
Pages302-313
ISBN (Print)978-3-642-22299-3
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6844
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'On rectilinear partitions with minimum stabbing number'. Together they form a unique fingerprint.

Cite this