On the rectangle escape problem

Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Research output: Contribution to conferencePaperpeer-review

6 Scopus citations

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(n4) time, improving upon the current best O(n6)-time algorithm.

Original languageEnglish (US)
Pages235-240
Number of pages6
StatePublished - 2013
Externally publishedYes
Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
Duration: Aug 8 2013Aug 10 2013

Conference

Conference25th Canadian Conference on Computational Geometry, CCCG 2013
Country/TerritoryCanada
CityWaterloo
Period8/8/138/10/13

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'On the rectangle escape problem'. Together they form a unique fingerprint.

Cite this