Decomposition and intersection of simple splinegons

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

doi:10.1007/BF01762127

Decomposition and intersection of simple splinegons

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	473-485
Number of pages	13
Journal	Algorithmica
Volume	3
Issue number	1
DOIs	https://doi.org/10.1007/BF01762127
State	Published - 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

Access to Document

10.1007/BF01762127

Cite this

@article{c37354b746654de7982e0a9178754e55,

title = "Decomposition and intersection of simple splinegons",

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

keywords = "Computational geometry, Convex decomposition, Curves, Intersection detection, Monotone decomposition, Simplicity testing",

author = "Dobkin, {David P.} and Souvaine, {Diane L.} and {Van Wyk}, {Christopher J.}",

year = "1988",

month = mar,

day = "1",

doi = "10.1007/BF01762127",

language = "English (US)",

volume = "3",

pages = "473--485",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Decomposition and intersection of simple splinegons

AU - Dobkin, David P.

AU - Souvaine, Diane L.

AU - Van Wyk, Christopher J.

PY - 1988/3/1

Y1 - 1988/3/1

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

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

KW - Computational geometry

KW - Convex decomposition

KW - Curves

KW - Intersection detection

KW - Monotone decomposition

KW - Simplicity testing

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

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

U2 - 10.1007/BF01762127

DO - 10.1007/BF01762127

M3 - Article

AN - SCOPUS:52449149129

SN - 0178-4617

VL - 3

SP - 473

EP - 485

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Decomposition and intersection of simple splinegons

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this