Convexifying polygons with simple projections

Jorge Alberto Calvo; Danny Krizanc; Pat Morin; Michael Soss; Godfried Toussaint

doi:10.1016/S0020-0190(01)00150-8

Convexifying polygons with simple projections

Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint

Computer Science

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

Abstract

It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal projection onto some plane, then the 3D polygon can be convexified. If an algorithm to convexify the planar projection exists and runs in time P, then our algorithm to convexify the 3D polygon runs in O(n + P) time.

Original language	English (US)
Pages (from-to)	81-86
Number of pages	6
Journal	Information Processing Letters
Volume	80
Issue number	2
DOIs	https://doi.org/10.1016/S0020-0190(01)00150-8
State	Published - Oct 31 2001

Keywords

Computational biology
Computational geometry
Convexification of polygons
Linkage reconfiguration
Motion planning
Polymer physics
Simple orthogonal projections

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/S0020-0190(01)00150-8

Cite this

@article{f84436e5e62f445882e36379b844c502,

title = "Convexifying polygons with simple projections",

abstract = "It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal projection onto some plane, then the 3D polygon can be convexified. If an algorithm to convexify the planar projection exists and runs in time P, then our algorithm to convexify the 3D polygon runs in O(n + P) time.",

keywords = "Computational biology, Computational geometry, Convexification of polygons, Linkage reconfiguration, Motion planning, Polymer physics, Simple orthogonal projections",

author = "Calvo, {Jorge Alberto} and Danny Krizanc and Pat Morin and Michael Soss and Godfried Toussaint",

year = "2001",

month = oct,

day = "31",

doi = "10.1016/S0020-0190(01)00150-8",

language = "English (US)",

volume = "80",

pages = "81--86",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Convexifying polygons with simple projections

AU - Calvo, Jorge Alberto

AU - Krizanc, Danny

AU - Morin, Pat

AU - Soss, Michael

AU - Toussaint, Godfried

PY - 2001/10/31

Y1 - 2001/10/31

N2 - It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal projection onto some plane, then the 3D polygon can be convexified. If an algorithm to convexify the planar projection exists and runs in time P, then our algorithm to convexify the 3D polygon runs in O(n + P) time.

AB - It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal projection onto some plane, then the 3D polygon can be convexified. If an algorithm to convexify the planar projection exists and runs in time P, then our algorithm to convexify the 3D polygon runs in O(n + P) time.

KW - Computational biology

KW - Computational geometry

KW - Convexification of polygons

KW - Linkage reconfiguration

KW - Motion planning

KW - Polymer physics

KW - Simple orthogonal projections

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

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

U2 - 10.1016/S0020-0190(01)00150-8

DO - 10.1016/S0020-0190(01)00150-8

M3 - Article

AN - SCOPUS:0035980569

SN - 0020-0190

VL - 80

SP - 81

EP - 86

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Convexifying polygons with simple projections

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this