## Abstract

Motivated by a bus routing application, we study the following rectangle escape problem: Given a set S of n rectangles inside a rectangular region R, extend each rectangle in S toward one of the four borders of R so that the maximum density over the region R is minimized, where the density of each point p ε R is defined as the number of extended rectangles containing p. We show that the problem is hard to approximate to within a factor better than 3/2 in general. When the optimal density is sufficiently large, we provide a randomized algorithm that achieves an approximation factor of 1+ ε with high probability improving upon the current best 4-approximation algorithm available for the problem. When the optimal density is one, we provide an exact algorithm that finds an optimal solution in O(n^{4}) time, improving upon the current best O(n^{6})-time algorithm.

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

Pages | 235-240 |

Number of pages | 6 |

State | Published - 2013 |

Externally published | Yes |

Event | 25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada Duration: Aug 8 2013 → Aug 10 2013 |

### Conference

Conference | 25th Canadian Conference on Computational Geometry, CCCG 2013 |
---|---|

Country/Territory | Canada |

City | Waterloo |

Period | 8/8/13 → 8/10/13 |

## All Science Journal Classification (ASJC) codes

- Geometry and Topology
- Computational Mathematics