1986 · 25 citations · 8 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryCombinatorial OptimizationGraph AlgorithmsRoutingVoronoi DiagramsFast HeuristicsGeneralized Voronoi DiagramsHeuristicsPlane Sweep PartitioningPolygon PartitioningVery-large-scale Integration (Vlsi) DesignVlsi ImplementationVoronoi Diagram Decomposition
We consider the problem of partitioning isothetic polygons into rectangles by drawing edges of minimum total length. The problem has various applications [LPRS], eg. in VLSI design when dividing routing regions into channels ([Riv1], [Riv2]). If the polygons contain holes, the problem in NP-hard [LPRS]. In this paper it is shown how solutions within a constant factor of the optimum can be computed in time Ο(n log n), thus improving the previous Ο(n2) time bound. An unusual divide-and-conquer technique is employed, involving alternating search from two opposite directions, and further efficiency is gained by using a fast method to sort subsets of points. Generalized Voronoi diagrams are used in combination with plane-sweeping in order to detect all “well bounded” rectangles, which are essential for the heuristic.
8
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Voronoi diagrams based on convex distance functions
L. Paul Chew, Robert L. Dyrsdale · 1985 · 225 citations
On triangulations of a set of points in the plane
Errol L. Lloyd · 1977 · 116 citations · Full text