Cutting a country for smallest square fit

Marc van Kreveld, Bettina Speckmann

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

6 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages91-102
Number of pages12
ISBN (Print)3-540-00142-5, 9783540001423
DOIs
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

Conference

Conference13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
CountryCanada
CityVancouver, BC
Period21/11/0223/11/02

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

Cite this