On the separability of quadrilaterals in the plane by translations and rotations

Michael E. Houle; Godfried T. Toussaint

doi:10.1007/s13366-016-0323-5

On the separability of quadrilaterals in the plane by translations and rotations

Michael E. Houle, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A proof is given that for all positive integers n≥ 7 there exist sets of n non-overlapping quadrilaterals in the plane, such that no non-empty proper subset of these quadrilaterals can be separated from its complement, as one rigid object, by a single translation, without disturbing its complement. Furthermore, examples are given for which no single quadrilateral can be separated from the others by means of translations or rotations.

Original language	English (US)
Pages (from-to)	267-276
Number of pages	10
Journal	Beitrage zur Algebra und Geometrie
Volume	58
Issue number	2
DOIs	https://doi.org/10.1007/s13366-016-0323-5
State	Published - Jun 1 2017

Keywords

Collision avoidance
Discrete and computational geometry
Interlocking polygons
Object mobility
Robotics
Spatial planning

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology

Access to Document

10.1007/s13366-016-0323-5

Cite this

@article{27d57c737d7341b9945d2477461e67ce,

title = "On the separability of quadrilaterals in the plane by translations and rotations",

abstract = "A proof is given that for all positive integers n≥ 7 there exist sets of n non-overlapping quadrilaterals in the plane, such that no non-empty proper subset of these quadrilaterals can be separated from its complement, as one rigid object, by a single translation, without disturbing its complement. Furthermore, examples are given for which no single quadrilateral can be separated from the others by means of translations or rotations.",

keywords = "Collision avoidance, Discrete and computational geometry, Interlocking polygons, Object mobility, Robotics, Spatial planning",

author = "Houle, {Michael E.} and Toussaint, {Godfried T.}",

note = "Funding Information: The research of the second author was supported by a grant from the Provost{\textquoteright}s Office of New York University Abu Dhabi, through the Faculty of Science, in Abu Dhabi, The United Arab Emirates. Publisher Copyright: {\textcopyright} 2016, The Managing Editors.",

year = "2017",

month = jun,

day = "1",

doi = "10.1007/s13366-016-0323-5",

language = "English (US)",

volume = "58",

pages = "267--276",

journal = "Beitrage zur Algebra und Geometrie",

issn = "0138-4821",

publisher = "Springer Berlin",

number = "2",

}

TY - JOUR

T1 - On the separability of quadrilaterals in the plane by translations and rotations

AU - Houle, Michael E.

AU - Toussaint, Godfried T.

N1 - Funding Information: The research of the second author was supported by a grant from the Provost’s Office of New York University Abu Dhabi, through the Faculty of Science, in Abu Dhabi, The United Arab Emirates. Publisher Copyright: © 2016, The Managing Editors.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - A proof is given that for all positive integers n≥ 7 there exist sets of n non-overlapping quadrilaterals in the plane, such that no non-empty proper subset of these quadrilaterals can be separated from its complement, as one rigid object, by a single translation, without disturbing its complement. Furthermore, examples are given for which no single quadrilateral can be separated from the others by means of translations or rotations.

AB - A proof is given that for all positive integers n≥ 7 there exist sets of n non-overlapping quadrilaterals in the plane, such that no non-empty proper subset of these quadrilaterals can be separated from its complement, as one rigid object, by a single translation, without disturbing its complement. Furthermore, examples are given for which no single quadrilateral can be separated from the others by means of translations or rotations.

KW - Collision avoidance

KW - Discrete and computational geometry

KW - Interlocking polygons

KW - Object mobility

KW - Robotics

KW - Spatial planning

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

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

U2 - 10.1007/s13366-016-0323-5

DO - 10.1007/s13366-016-0323-5

M3 - Article

AN - SCOPUS:85019352481

SN - 0138-4821

VL - 58

SP - 267

EP - 276

JO - Beitrage zur Algebra und Geometrie

JF - Beitrage zur Algebra und Geometrie

IS - 2

ER -

On the separability of quadrilaterals in the plane by translations and rotations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this