Polygonal chain simplification with small angle constraints

Ovidiu Daescu; Anastasia Kurdia

Polygonal chain simplification with small angle constraints

Ovidiu Daescu, Anastasia Kurdia

Computer Science

Research output: Contribution to conference › Paper › peer-review

2 Scopus citations

Abstract

We consider the problem of simplifying an n-vertex polygonal chain with small angle constraints in ℝ² and ℝ³, thus closing the gap on the range of angles left in previous work on the problem. Specifically, we show that the min-# version of the polygonal chain simplification problem with small angle constraints can be solved in O(n ²) time and space in ℝ², and in O(n² log² n) time, O(n²) space in ℝ³.

Original language	English (US)
Pages	191-194
Number of pages	4
State	Published - 2008
Event	20th Annual Canadian Conference on Computational Geometry, CCCG 2008 - Montreal, QC, Canada Duration: Aug 13 2008 → Aug 15 2008

Conference

Conference	20th Annual Canadian Conference on Computational Geometry, CCCG 2008
Country/Territory	Canada
City	Montreal, QC
Period	8/13/08 → 8/15/08

ASJC Scopus subject areas

Geometry and Topology

Cite this

@conference{4d3bbd9df8804db882effc1718046b58,

title = "Polygonal chain simplification with small angle constraints",

abstract = "We consider the problem of simplifying an n-vertex polygonal chain with small angle constraints in ℝ2 and ℝ3, thus closing the gap on the range of angles left in previous work on the problem. Specifically, we show that the min-# version of the polygonal chain simplification problem with small angle constraints can be solved in O(n 2) time and space in ℝ2, and in O(n2 log2 n) time, O(n2) space in ℝ3.",

author = "Ovidiu Daescu and Anastasia Kurdia",

year = "2008",

language = "English (US)",

pages = "191--194",

note = "20th Annual Canadian Conference on Computational Geometry, CCCG 2008 ; Conference date: 13-08-2008 Through 15-08-2008",

}

TY - CONF

T1 - Polygonal chain simplification with small angle constraints

AU - Daescu, Ovidiu

AU - Kurdia, Anastasia

PY - 2008

Y1 - 2008

N2 - We consider the problem of simplifying an n-vertex polygonal chain with small angle constraints in ℝ2 and ℝ3, thus closing the gap on the range of angles left in previous work on the problem. Specifically, we show that the min-# version of the polygonal chain simplification problem with small angle constraints can be solved in O(n 2) time and space in ℝ2, and in O(n2 log2 n) time, O(n2) space in ℝ3.

AB - We consider the problem of simplifying an n-vertex polygonal chain with small angle constraints in ℝ2 and ℝ3, thus closing the gap on the range of angles left in previous work on the problem. Specifically, we show that the min-# version of the polygonal chain simplification problem with small angle constraints can be solved in O(n 2) time and space in ℝ2, and in O(n2 log2 n) time, O(n2) space in ℝ3.

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

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

M3 - Paper

AN - SCOPUS:84893358535

SP - 191

EP - 194

T2 - 20th Annual Canadian Conference on Computational Geometry, CCCG 2008

Y2 - 13 August 2008 through 15 August 2008

ER -

Polygonal chain simplification with small angle constraints

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this