Cutting a country for smallest square fit

Marc van Kreveld; Bettina Speckmann

doi:10.1007/3-540-36136-7_9

Cutting a country for smallest square fit

Marc van Kreveld, Bettina Speckmann

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

1 Downloads (Pure)

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(n⁴α(n) logn) time algorithm.

Original language	English
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Editors	Prosenjit Bose, Pat Morin
Place of Publication	Berlin
Publisher	Springer
Pages	91-102
Number of pages	12
ISBN (Print)	3-540-00142-5, 9783540001423
DOIs	https://doi.org/10.1007/3-540-36136-7_9
Publication status	Published - 1 Dec 2002
Externally published	Yes
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: 21 Nov 2002 → 23 Nov 2002

Publication series

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

Conference

Conference	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	21/11/02 → 23/11/02

Access to Document

10.1007/3-540-36136-7_9

Cite this

van Kreveld, M., & Speckmann, B. (2002). Cutting a country for smallest square fit. In P. Bose, & P. Morin (Eds.), Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 91-102). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). Springer. https://doi.org/10.1007/3-540-36136-7_9

van Kreveld, Marc ; Speckmann, Bettina. / Cutting a country for smallest square fit. Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. editor / Prosenjit Bose ; Pat Morin. Berlin : Springer, 2002. pp. 91-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0257d3a8a3a74e298887f1c67104fb29,

title = "Cutting a country for smallest square fit",

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.",

author = "{van Kreveld}, Marc and Bettina Speckmann",

year = "2002",

month = dec,

day = "1",

doi = "10.1007/3-540-36136-7_9",

language = "English",

isbn = "3-540-00142-5",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "91--102",

editor = "Prosenjit Bose and Pat Morin",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

van Kreveld, M & Speckmann, B 2002, Cutting a country for smallest square fit. in P Bose & P Morin (eds), Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, Springer, Berlin, pp. 91-102, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 21/11/02. https://doi.org/10.1007/3-540-36136-7_9

Cutting a country for smallest square fit. / van Kreveld, Marc; Speckmann, Bettina.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. ed. / Prosenjit Bose; Pat Morin. Berlin: Springer, 2002. p. 91-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Cutting a country for smallest square fit

AU - van Kreveld, Marc

AU - Speckmann, Bettina

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84878623984&partnerID=8YFLogxK

U2 - 10.1007/3-540-36136-7_9

DO - 10.1007/3-540-36136-7_9

M3 - Conference contribution

AN - SCOPUS:84878623984

SN - 3-540-00142-5

SN - 9783540001423

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 91

EP - 102

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

A2 - Bose, Prosenjit

A2 - Morin, Pat

PB - Springer

CY - Berlin

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

van Kreveld M, Speckmann B. Cutting a country for smallest square fit. In Bose P, Morin P, editors, Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Berlin: Springer. 2002. p. 91-102. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36136-7_9

Cutting a country for smallest square fit

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this