CIM algorithm for approximating three-dimensional polygonal curves View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-11

AUTHORS

Junhai Yong, Shimin Hu, Jiaguang Sun

ABSTRACT

The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. InR2, the cone intersection method (CIM) is one of the most efficient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) underL2 norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity isO(n3), and the space complexity isO(n2). An approximation algorithm is also presented, which takesO(n2) time andO(n) space. Results of some examples are given to illustrate the efficiency of these algorithms. More... »

PAGES

552-559

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02943239

DOI

http://dx.doi.org/10.1007/bf02943239

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1015757261


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "National CAD Engineering Center, Tsinghua University, 100084, Beijing, P.R. China", 
            "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yong", 
        "givenName": "Junhai", 
        "id": "sg:person.01071075202.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01071075202.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "National CAD Engineering Center, Tsinghua University, 100084, Beijing, P.R. China", 
            "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hu", 
        "givenName": "Shimin", 
        "id": "sg:person.013413402617.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013413402617.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "National CAD Engineering Center, Tsinghua University, 100084, Beijing, P.R. China", 
            "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sun", 
        "givenName": "Jiaguang", 
        "id": "sg:person.011411464635.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-11", 
    "datePublishedReg": "2001-11-01", 
    "description": "The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. InR2, the cone intersection method (CIM) is one of the most efficient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) underL2 norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity isO(n3), and the space complexity isO(n2). An approximation algorithm is also presented, which takesO(n2) time andO(n) space. Results of some examples are given to illustrate the efficiency of these algorithms.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02943239", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1357568", 
        "issn": [
          "1000-9000", 
          "1860-4749"
        ], 
        "name": "Journal of Computer Science and Technology", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "6", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "16"
      }
    ], 
    "keywords": [
      "cone intersection method", 
      "polygonal approximation problem", 
      "error criterion", 
      "polygonal curves", 
      "approximation problem", 
      "time complexity", 
      "computer graphics", 
      "additional constraints", 
      "CIM solutions", 
      "space complexity", 
      "pattern recognition", 
      "efficient algorithm", 
      "approximation algorithm", 
      "CAD/CAM", 
      "algorithm", 
      "intersection method", 
      "same problem", 
      "complexity", 
      "constraints", 
      "primary problem", 
      "graphics", 
      "recognition", 
      "space", 
      "efficiency", 
      "example", 
      "solution", 
      "criteria", 
      "method", 
      "time", 
      "CAM", 
      "results", 
      "inR2", 
      "Toussaint", 
      "curves", 
      "norms", 
      "EU", 
      "changes", 
      "problem", 
      "paper", 
      "CIM Eu", 
      "minimum number polygonal approximation problem", 
      "number polygonal approximation problem", 
      "parallel-strip error criterion", 
      "line segment error criterion", 
      "segment error criterion", 
      "PS-WMN", 
      "three-dimensional polygonal curves"
    ], 
    "name": "CIM algorithm for approximating three-dimensional polygonal curves", 
    "pagination": "552-559", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015757261"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02943239"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02943239", 
      "https://app.dimensions.ai/details/publication/pub.1015757261"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_312.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02943239"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02943239'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02943239'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02943239'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02943239'


 

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      21 PREDICATES      73 URIs      65 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02943239 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfe58410eb91945f5b363d37f4dae8028
4 schema:datePublished 2001-11
5 schema:datePublishedReg 2001-11-01
6 schema:description The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. InR2, the cone intersection method (CIM) is one of the most efficient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) underL2 norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity isO(n3), and the space complexity isO(n2). An approximation algorithm is also presented, which takesO(n2) time andO(n) space. Results of some examples are given to illustrate the efficiency of these algorithms.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N172b49345ea246129a7b4ed62836e3c3
11 N35f656706e4242db8b0e8c7e2a1f3f51
12 sg:journal.1357568
13 schema:keywords CAD/CAM
14 CAM
15 CIM Eu
16 CIM solutions
17 EU
18 PS-WMN
19 Toussaint
20 additional constraints
21 algorithm
22 approximation algorithm
23 approximation problem
24 changes
25 complexity
26 computer graphics
27 cone intersection method
28 constraints
29 criteria
30 curves
31 efficiency
32 efficient algorithm
33 error criterion
34 example
35 graphics
36 inR2
37 intersection method
38 line segment error criterion
39 method
40 minimum number polygonal approximation problem
41 norms
42 number polygonal approximation problem
43 paper
44 parallel-strip error criterion
45 pattern recognition
46 polygonal approximation problem
47 polygonal curves
48 primary problem
49 problem
50 recognition
51 results
52 same problem
53 segment error criterion
54 solution
55 space
56 space complexity
57 three-dimensional polygonal curves
58 time
59 time complexity
60 schema:name CIM algorithm for approximating three-dimensional polygonal curves
61 schema:pagination 552-559
62 schema:productId N0448235c91ca4a2192b3333c63a8c8a1
63 N1056629ad96d467db4fcf1a37df7dd7d
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015757261
65 https://doi.org/10.1007/bf02943239
66 schema:sdDatePublished 2022-01-01T18:09
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N22bb1dafc5d349aab613db50f30676aa
69 schema:url https://doi.org/10.1007/bf02943239
70 sgo:license sg:explorer/license/
71 sgo:sdDataset articles
72 rdf:type schema:ScholarlyArticle
73 N0448235c91ca4a2192b3333c63a8c8a1 schema:name dimensions_id
74 schema:value pub.1015757261
75 rdf:type schema:PropertyValue
76 N1056629ad96d467db4fcf1a37df7dd7d schema:name doi
77 schema:value 10.1007/bf02943239
78 rdf:type schema:PropertyValue
79 N172b49345ea246129a7b4ed62836e3c3 schema:volumeNumber 16
80 rdf:type schema:PublicationVolume
81 N22bb1dafc5d349aab613db50f30676aa schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 N35f656706e4242db8b0e8c7e2a1f3f51 schema:issueNumber 6
84 rdf:type schema:PublicationIssue
85 N4caffb53ae96487ca5cf681644051b52 rdf:first sg:person.011411464635.59
86 rdf:rest rdf:nil
87 N4eafa863414f4a848c3c7dc0f0f8afb9 rdf:first sg:person.013413402617.49
88 rdf:rest N4caffb53ae96487ca5cf681644051b52
89 Nfe58410eb91945f5b363d37f4dae8028 rdf:first sg:person.01071075202.49
90 rdf:rest N4eafa863414f4a848c3c7dc0f0f8afb9
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:journal.1357568 schema:issn 1000-9000
98 1860-4749
99 schema:name Journal of Computer Science and Technology
100 schema:publisher Springer Nature
101 rdf:type schema:Periodical
102 sg:person.01071075202.49 schema:affiliation grid-institutes:grid.12527.33
103 schema:familyName Yong
104 schema:givenName Junhai
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01071075202.49
106 rdf:type schema:Person
107 sg:person.011411464635.59 schema:affiliation grid-institutes:grid.12527.33
108 schema:familyName Sun
109 schema:givenName Jiaguang
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59
111 rdf:type schema:Person
112 sg:person.013413402617.49 schema:affiliation grid-institutes:grid.12527.33
113 schema:familyName Hu
114 schema:givenName Shimin
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013413402617.49
116 rdf:type schema:Person
117 grid-institutes:grid.12527.33 schema:alternateName Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China
118 schema:name Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, P.R. China
119 National CAD Engineering Center, Tsinghua University, 100084, Beijing, P.R. China
120 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...