Convexifying polygons with simple projections

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

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)81-86
Number of pages6
JournalInformation Processing Letters
Volume80
Issue number2
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Convexifying polygons with simple projections'. Together they form a unique fingerprint.

  • Cite this