Decomposition and intersection of simple splinegons

David P. Dobkin, Diane L. Souvaine, Christopher J. Van Wyk

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

A splinegon is a polygon whose edges have been replaced by "well-behaved" curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.

Original languageEnglish (US)
Pages (from-to)473-485
Number of pages13
JournalAlgorithmica
Volume3
Issue number1
DOIs
StatePublished - Mar 1 1988

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Computational geometry
  • Convex decomposition
  • Curves
  • Intersection detection
  • Monotone decomposition
  • Simplicity testing

Fingerprint

Dive into the research topics of 'Decomposition and intersection of simple splinegons'. Together they form a unique fingerprint.

Cite this