Parallel Algorithms for Identification of Basis Polygons in an Image View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Arijit Laha , Amitava Sen , Bhabani P. Sinha

ABSTRACT

Given a set of n straight line segments each described by its two end points, we propose two novel algorithms for detecting all basis polygons formed by them. The algorithms, based on traversals along the sides of the basis polygons, detect the polygons in O(n) time using n2 processors. The first algorithm handles the simple scenes consisting of convex basis polygons only, while the second one deals with the general situation. These algorithms have been simulated and tested for a number of input sets of intersecting line segments. More... »

PAGES

302-312

Book

TITLE

High Performance Computing — HiPC 2002

ISBN

978-3-540-00303-8
978-3-540-36265-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36265-7_29

DOI

http://dx.doi.org/10.1007/3-540-36265-7_29

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "National Institute of Management Calcutta, 700027\u00a0Alipore, Calcutta, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Laha", 
        "givenName": "Arijit", 
        "id": "sg:person.011633466625.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011633466625.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Statistical Institute", 
          "id": "https://www.grid.ac/institutes/grid.39953.35", 
          "name": [
            "ACM Unit, Indian Statistical Institute, 700 108\u00a0Calcutta, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sen", 
        "givenName": "Amitava", 
        "id": "sg:person.016412363334.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016412363334.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Statistical Institute", 
          "id": "https://www.grid.ac/institutes/grid.39953.35", 
          "name": [
            "ACM Unit, Indian Statistical Institute, 700 108\u00a0Calcutta, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sinha", 
        "givenName": "Bhabani P.", 
        "id": "sg:person.016102452535.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016102452535.25"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(79)90069-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010472559"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jpdc.1998.1514", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014341866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(87)90086-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019088682"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(87)90086-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019088682"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(87)90067-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024536609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(87)90067-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024536609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02243778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032338660", 
          "https://doi.org/10.1007/bf02243778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02243778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032338660", 
          "https://doi.org/10.1007/bf02243778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01898355", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034934409", 
          "https://doi.org/10.1007/bf01898355"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01898355", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034934409", 
          "https://doi.org/10.1007/bf01898355"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/361237.361242", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037839065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0146-664x(82)90023-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048751598"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002", 
    "datePublishedReg": "2002-01-01", 
    "description": "Given a set of n straight line segments each described by its two end points, we propose two novel algorithms for detecting all basis polygons formed by them. The algorithms, based on traversals along the sides of the basis polygons, detect the polygons in O(n) time using n2 processors. The first algorithm handles the simple scenes consisting of convex basis polygons only, while the second one deals with the general situation. These algorithms have been simulated and tested for a number of input sets of intersecting line segments.", 
    "editor": [
      {
        "familyName": "Sahni", 
        "givenName": "Sartaj", 
        "type": "Person"
      }, 
      {
        "familyName": "Prasanna", 
        "givenName": "Viktor K.", 
        "type": "Person"
      }, 
      {
        "familyName": "Shukla", 
        "givenName": "Uday", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36265-7_29", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00303-8", 
        "978-3-540-36265-4"
      ], 
      "name": "High Performance Computing \u2014 HiPC 2002", 
      "type": "Book"
    }, 
    "name": "Parallel Algorithms for Identification of Basis Polygons in an Image", 
    "pagination": "302-312", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36265-7_29"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5e7cc66c5ceb4d19ad7edd196ef2425d78ac05bf9105cdce9c7353920023d3b9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019831215"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36265-7_29", 
      "https://app.dimensions.ai/details/publication/pub.1019831215"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:24", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000255.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-36265-7_29"
  }
]
 

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/3-540-36265-7_29'

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/3-540-36265-7_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36265-7_29'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36265-7_29'


 

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

117 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36265-7_29 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nb2a5de75bffc497281269ab0688bc057
4 schema:citation sg:pub.10.1007/bf01898355
5 sg:pub.10.1007/bf02243778
6 https://doi.org/10.1006/jpdc.1998.1514
7 https://doi.org/10.1016/0020-0190(79)90069-3
8 https://doi.org/10.1016/0020-0190(87)90086-x
9 https://doi.org/10.1016/0031-3203(87)90067-7
10 https://doi.org/10.1016/0146-664x(82)90023-5
11 https://doi.org/10.1145/361237.361242
12 schema:datePublished 2002
13 schema:datePublishedReg 2002-01-01
14 schema:description Given a set of n straight line segments each described by its two end points, we propose two novel algorithms for detecting all basis polygons formed by them. The algorithms, based on traversals along the sides of the basis polygons, detect the polygons in O(n) time using n2 processors. The first algorithm handles the simple scenes consisting of convex basis polygons only, while the second one deals with the general situation. These algorithms have been simulated and tested for a number of input sets of intersecting line segments.
15 schema:editor Na3b242ddd6e843ecba34bde959a4c9bc
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf Ndf961a70f3d14ad1be9417dc499a58bc
20 schema:name Parallel Algorithms for Identification of Basis Polygons in an Image
21 schema:pagination 302-312
22 schema:productId N4709921335d94704bb66712d769cdc08
23 N4cb72ccccd01481c9db704f0d302a63d
24 N9a6f846a7efe44ca84c6dcb58276d2f3
25 schema:publisher N2e5b06bb4301423682c7244a5c52db80
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019831215
27 https://doi.org/10.1007/3-540-36265-7_29
28 schema:sdDatePublished 2019-04-15T14:24
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N68a7b6930bc0460d803090b0caff485e
31 schema:url http://link.springer.com/10.1007/3-540-36265-7_29
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N289a6675315e408b9b3590d74b6f4704 rdf:first Nc53393c6a25a46978c84dfbfb5902288
36 rdf:rest N50da2f15cd2c4752b00359bbb6200ce1
37 N2e5b06bb4301423682c7244a5c52db80 schema:location Berlin, Heidelberg
38 schema:name Springer Berlin Heidelberg
39 rdf:type schema:Organisation
40 N3f01c258e8224c7e8a7ce4e14b83477a rdf:first sg:person.016102452535.25
41 rdf:rest rdf:nil
42 N4709921335d94704bb66712d769cdc08 schema:name dimensions_id
43 schema:value pub.1019831215
44 rdf:type schema:PropertyValue
45 N4cb72ccccd01481c9db704f0d302a63d schema:name doi
46 schema:value 10.1007/3-540-36265-7_29
47 rdf:type schema:PropertyValue
48 N50da2f15cd2c4752b00359bbb6200ce1 rdf:first Nc4602f4ee0d84331a4e8a8b1d96e8f46
49 rdf:rest rdf:nil
50 N50ebaeb92536418996abb72dc30738cf schema:name National Institute of Management Calcutta, 700027 Alipore, Calcutta, India
51 rdf:type schema:Organization
52 N68a7b6930bc0460d803090b0caff485e schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N9a6f846a7efe44ca84c6dcb58276d2f3 schema:name readcube_id
55 schema:value 5e7cc66c5ceb4d19ad7edd196ef2425d78ac05bf9105cdce9c7353920023d3b9
56 rdf:type schema:PropertyValue
57 Na3b242ddd6e843ecba34bde959a4c9bc rdf:first Nd422b2a05a2145089b7d3524566e9a09
58 rdf:rest N289a6675315e408b9b3590d74b6f4704
59 Nb2a5de75bffc497281269ab0688bc057 rdf:first sg:person.011633466625.33
60 rdf:rest Nf9500f657e1a4da5b9a7522328191522
61 Nc4602f4ee0d84331a4e8a8b1d96e8f46 schema:familyName Shukla
62 schema:givenName Uday
63 rdf:type schema:Person
64 Nc53393c6a25a46978c84dfbfb5902288 schema:familyName Prasanna
65 schema:givenName Viktor K.
66 rdf:type schema:Person
67 Nd422b2a05a2145089b7d3524566e9a09 schema:familyName Sahni
68 schema:givenName Sartaj
69 rdf:type schema:Person
70 Ndf961a70f3d14ad1be9417dc499a58bc schema:isbn 978-3-540-00303-8
71 978-3-540-36265-4
72 schema:name High Performance Computing — HiPC 2002
73 rdf:type schema:Book
74 Nf9500f657e1a4da5b9a7522328191522 rdf:first sg:person.016412363334.05
75 rdf:rest N3f01c258e8224c7e8a7ce4e14b83477a
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
80 schema:name Artificial Intelligence and Image Processing
81 rdf:type schema:DefinedTerm
82 sg:person.011633466625.33 schema:affiliation N50ebaeb92536418996abb72dc30738cf
83 schema:familyName Laha
84 schema:givenName Arijit
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011633466625.33
86 rdf:type schema:Person
87 sg:person.016102452535.25 schema:affiliation https://www.grid.ac/institutes/grid.39953.35
88 schema:familyName Sinha
89 schema:givenName Bhabani P.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016102452535.25
91 rdf:type schema:Person
92 sg:person.016412363334.05 schema:affiliation https://www.grid.ac/institutes/grid.39953.35
93 schema:familyName Sen
94 schema:givenName Amitava
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016412363334.05
96 rdf:type schema:Person
97 sg:pub.10.1007/bf01898355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034934409
98 https://doi.org/10.1007/bf01898355
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf02243778 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338660
101 https://doi.org/10.1007/bf02243778
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1006/jpdc.1998.1514 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014341866
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/0020-0190(79)90069-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010472559
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/0020-0190(87)90086-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1019088682
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0031-3203(87)90067-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024536609
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/0146-664x(82)90023-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048751598
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/361237.361242 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037839065
114 rdf:type schema:CreativeWork
115 https://www.grid.ac/institutes/grid.39953.35 schema:alternateName Indian Statistical Institute
116 schema:name ACM Unit, Indian Statistical Institute, 700 108 Calcutta, India
117 rdf:type schema:Organization
 




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


...