Browsing by Author "Chadha, Ritu"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Decomposing Rectilinear Figures into Rectangles
    Chadha, Ritu; Allison, Donald C. S. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)
    We discuss the problem of decomposing rectilinear regions, with or without holes, into a minimum number of rectangles. There are two different problems considered here: decomposing a figure into non-overlapping parts, called partitioning, and decomposing a figure into possibly overlapping parts, called covering. A method is outlined and proved for solving the above two problems, and algorithms for the solutions of these problems are presented. The partitioning problem can be solved in time O(n-to the 5/2), where n is the number of vertices of the figure, whereas the covering problem is exponential in its time complexity.
  • Thumbnail Image
    Decomposing rectilinear regions into rectangles
    Chadha, Ritu (Virginia Polytechnic Institute and State University, 1987)
    This thesis discusses the problem of decomposing rectilinear regions, with or without holes, into a minimum number of rectangles. There are two different types of decomposition considered here : decomposing a figure into non-overlapping parts, called partitioning, and decomposing a figure into possibly overlapping parts, called covering. A method is outlined and proved for solving the above two problems, and algorithms for the solutions of these problems are presented. The partitioning problem can be solved in time O(n⁵ ²), where n is the number of vertices of the figure, whereas the covering problem is exponential in its time complexity.
  • Thumbnail Image
    An O(N log N) Expected Time Merge Heuristic for the Planar ETSP
    Chadha, Ritu; Allison, Donald C. S. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)
    We discuss a new heuristic for solving the Euclidean Traveling Salesman Problem (ETSP). This heuristic is a convex hull-based method and makes use of the Delaunay triangulation of the set of cities to compute a tour for the given set of cities. We conjecture that the expected running time for this algorithm is O(N log N), implying that a new and faster ETSP heuristic is now available.