@inproceedings{8517c7ab4eac411ba14670b465c10e84,
title = "On rectilinear partitions with minimum stabbing number",
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'.",
author = "{Berg, de}, M.T. and {Khosravi Dehkordi}, A. and S. Verdonschot and {Weele, van der}, V.",
year = "2011",
doi = "10.1007/978-3-642-22300-6_26",
language = "English",
isbn = "978-3-642-22299-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "302--313",
editor = "F. Dehne and J. Iacono and F.R. Sack",
booktitle = "Algorithms and Data Structures (12th International Workshop, WADS 2011, Brooklyn NY, USA, August 15-17, 2011. Proceedings)",
address = "Germany",
}