Article

Free access

Fast heuristics for minimum length rectangular partitions of polygons

Author:

C LevcopoulosAuthors Info & Claims

SCG '86: Proceedings of the second annual symposium on Computational geometry

Pages 100 - 108

https://doi.org/10.1145/10515.10526

Published: 01 August 1986 Publication History

Abstract

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 Ο(n²) 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.

References

[1]

Chew, L.P., and Drysdale, R.L., "Voronoi Diagrams Based on Convex Distance Functions", Proc. First ACM Symposium on Computational Geometry, Baltimore, June 1985.

Digital Library

[2]

Fortune, S.J., "A Fast Algorithm for Polygon Containment by Translation", Proc. 12th ICALP, Nafplion, Greece, 1985.

Digital Library

[3]

Gonzalez, T., and S.Q. Zheng, "Bounds for Partitioning Rectilinear Polygons' Proc. First ACM Symposium on Computational Geometry, Baltimore, June 1985.

Digital Library

[4]

Imai, H., and Asano, T., "Dynamic intersection Search with Applications", Proc. 25th iEEE FOCS Symp., Florida, 1984.

[5]

Keil, J.M., and J.R. Sack, "Minimum Decompositions of Polygonal Objects", SCS-TR-42, Carleton University, Ottawa.

[6]

Kirkpatrick, D.G., "An upper bound for sorting integers in restricted ranges", Proc. 18th Allerton Conf. on Comm. Control and Computing, Illinois, (Oct. 1980).

[7]

Levcopoulos, C., "Minimum Length and 'Thickest- First' Rectangular Partitions of Polygons", Proc. 23rd Allerton Conf. on Comm. Control and Computing, Illinois, October 1985.

[8]

Levcopoulos, C., "Heuristics for Decomposing Polygons into Rectangles" (preliminary title), in prepara~ tion, LinkSping.

[9]

Levcopoulos, C., and A. Lingas, "Bounds on the Length of Convex Partitions of Polygons", Proc. 4th Conf. on Found. of Software Technology and Theoretical Computer Science, Bangalore, India, 1984 (Springer Verlag).

Digital Library

[10]

Lingas, A., "Heuristics for Minimum Edge Length Rectangular Partitions of Rectilinear Figures", Proc. 6th GI-Conference, Dortmund, January 1983 (Springer Verlag).

Digital Library

[11]

Lloyd, E.L., "On Triangulations of a Set of Points in the Plane", Proc. of 18th IEEE Conf. on Foundations of Comp. Sc., Providence, 1977.

Digital Library

[12]

Lingas, A., R.Y. Pinter, R.L. Rivest, and A. Shamir, "Minimum Edge Length Partitioning of Rectilinear Polygons", Proc. 20th Allerton Conf. on Comm. Control and Compt., Illinois, 1982.

[13]

Preparata, F.P., and M.I. Shamos, "Computational Geometry", New York Springer-Verlag, 1985.

Digital Library

[14]

Rivest, R., "The PI (Placement and Interconnect) System", Proc. 19th Design Automation Conference, June 1982.

Digital Library

[15]

Rivest, R., Private Communication, October 1985.

Cited By

Kim HLee JAhn H(2023)Rectangular partitions of a rectilinear polygonComputational Geometry10.1016/j.comgeo.2022.101965110(101965)Online publication date: Mar-2023
https://doi.org/10.1016/j.comgeo.2022.101965
Du DPardalos PHu XWu WDu DPardalos PHu XWu W(2022)Restriction and Steiner TreeIntroduction to Combinatorial Optimization10.1007/978-3-031-10596-8_9(259-291)Online publication date: 6-Jul-2022
https://doi.org/10.1007/978-3-031-10596-8_9
Maheshwari ANandy SPattanayak DRoy SSmid M(2018)Geometric Path Problems with ViolationsAlgorithmica10.1007/s00453-016-0263-380:2(448-471)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00453-016-0263-3
Show More Cited By

Index Terms

Fast heuristics for minimum length rectangular partitions of polygons

Recommendations

Minimum rectangular partition problem for simple rectilinear polygons

An O( n log log n ) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P , a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical ...
Minimum-perimeter intersecting polygons
LATIN'10: Proceedings of the 9th Latin American conference on Theoretical Informatics

Given a set ${\mathcal S}$ of segments in the plane, a polygon P is an intersecting polygon of ${\mathcal S}$ if every segment in ${\mathcal S}$ intersects the interior or the boundary of P. The problem MPIP of computing a minimum-perimeter intersecting ...
Heuristics for minimum decompositions of polygons

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '86: Proceedings of the second annual symposium on Computational geometry

August 1986

322 pages

ISBN:0897911946

DOI:10.1145/10515

Chairman:
Alok Aggarwal

Copyright © 1986 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CG86

Sponsor:

CG86: The 2nd Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry

June 2 - 4, 1986

New York, Yorktown Heights, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
603
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)15

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim HLee JAhn H(2023)Rectangular partitions of a rectilinear polygonComputational Geometry10.1016/j.comgeo.2022.101965110(101965)Online publication date: Mar-2023
https://doi.org/10.1016/j.comgeo.2022.101965
Du DPardalos PHu XWu WDu DPardalos PHu XWu W(2022)Restriction and Steiner TreeIntroduction to Combinatorial Optimization10.1007/978-3-031-10596-8_9(259-291)Online publication date: 6-Jul-2022
https://doi.org/10.1007/978-3-031-10596-8_9
Maheshwari ANandy SPattanayak DRoy SSmid M(2018)Geometric Path Problems with ViolationsAlgorithmica10.1007/s00453-016-0263-380:2(448-471)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00453-016-0263-3
Ackerman EAllen MBarequet GLöffler MMermelstein JSouvaine DTóth C(2014)The Flip Diameter of Rectangulations and Convex SubdivisionsLATIN 2014: Theoretical Informatics10.1007/978-3-642-54423-1_42(478-489)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54423-1_42
Ackerman EBarequet GPinter R(2006)On the number of rectangulations of a planar point setJournal of Combinatorial Theory Series A10.1016/j.jcta.2005.10.003113:6(1072-1091)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1016/j.jcta.2005.10.003
Levcopoulos CÖstlin A(2005)Linear-time heuristics for minimum weight rectangulationAlgorithm Theory — SWAT'9610.1007/3-540-61422-2_138(271-283)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61422-2_138
Cheng XDu DKim JRuan L(2005)Optimal Rectangular PartitionsHandbook of Combinatorial Optimization10.1007/0-387-23830-1_7(313-327)Online publication date: 2005
https://doi.org/10.1007/0-387-23830-1_7
Ackerman EBarequet GPinter RMunro I(2004)On the number of rectangular partitionsProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982904(736-745)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982904
Cheng XDu DKim JNgo H(2002)Guillotine Cut in Approximation AlgorithmsCooperative Control and Optimization10.1007/0-306-47536-7_2(21-34)Online publication date: 2002
https://doi.org/10.1007/0-306-47536-7_2
Kahng AWiesel MHill D(2000)Classical floorplanning harmful?Proceedings of the 2000 international symposium on Physical design10.1145/332357.332401(207-213)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/332357.332401
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents