Cutting a country for smallest square fit

Marc van Kreveld, Bettina Speckmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


We study the problem of cutting a simple polygon with n vertices into two pieces such that - if we reposition one piece disjoint of the other, without rotation - they have the minimum possible bounding square. If we cut with a single horizontal or vertical segment, then we can compute an optimal solution for a convex polygon with n vertices in O(n) time. For simple polygons we give an O(n4α(n) logn) time algorithm.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
EditorsProsenjit Bose, Pat Morin
Place of PublicationBerlin
Number of pages12
ISBN (Print)3-540-00142-5, 9783540001423
Publication statusPublished - 1 Dec 2002
Externally publishedYes
Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
Duration: 21 Nov 200223 Nov 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2518 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
CityVancouver, BC


Dive into the research topics of 'Cutting a country for smallest square fit'. Together they form a unique fingerprint.

Cite this