### 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 line segment inside P. We present a 3-approximation algorithm for the problem of finding a partition with minimum stabbing number. It is based on an algorithm that finds an optimal partition for histograms. We also study Steiner triangulations of a simple (nonrectilinear) polygon P. Here the stabbing number is defined as the maximum number of triangles that can be stabbed by any line segment inside P. We give an O(1)-approximation algorithm for the problem of computing a Steiner triangulation with minimum stabbing number.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11 |

Pages | 407-416 |

Number of pages | 10 |

DOIs | |

State | Published - 2011 |

Event | 27th Annual ACM Symposium on Computational Geometry, SCG'11 - Paris, France Duration: Jun 13 2011 → Jun 15 2011 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 27th Annual ACM Symposium on Computational Geometry, SCG'11 |
---|---|

Country | France |

City | Paris |

Period | 6/13/11 → 6/15/11 |

### Keywords

- Approximation algorithms
- Computational geometry
- Polygons
- Rectangular decompositions
- Stabbing number
- Steiner triangulations

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11*(pp. 407-416). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1998196.1998263