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 Nbafaac12f4254b1b837ea82dc3c83e66
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 N4e6104cc0c8947539e75a9f41d308755
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N585f4c78ce3e4dc398200a5b3f5633e8
20 schema:name Parallel Algorithms for Identification of Basis Polygons in an Image
21 schema:pagination 302-312
22 schema:productId N1870348a4c9d4a10be2dc30c9d65d90c
23 N8aba29713531407db1bb356a4d7c00a9
24 Nefadfa32b0034c64a9bd050c3eab20a7
25 schema:publisher N7a5e3578ae1e483cb0b8ab2e3bfd6536
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 Ne317837cdcf44249bf445e1a0d363a53
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 N1870348a4c9d4a10be2dc30c9d65d90c schema:name dimensions_id
36 schema:value pub.1019831215
37 rdf:type schema:PropertyValue
38 N3b796f0e1a9540068b161cd6f6ab3c81 schema:familyName Shukla
39 schema:givenName Uday
40 rdf:type schema:Person
41 N4e6104cc0c8947539e75a9f41d308755 rdf:first Neee9d6ff410e4727bb84a5d2d2102d43
42 rdf:rest Ncffa1d935ecc48a7b606b8e7aa145170
43 N585f4c78ce3e4dc398200a5b3f5633e8 schema:isbn 978-3-540-00303-8
44 978-3-540-36265-4
45 schema:name High Performance Computing — HiPC 2002
46 rdf:type schema:Book
47 N7a5e3578ae1e483cb0b8ab2e3bfd6536 schema:location Berlin, Heidelberg
48 schema:name Springer Berlin Heidelberg
49 rdf:type schema:Organisation
50 N7fd6a59fe82b4546b96c043357b023dc rdf:first N3b796f0e1a9540068b161cd6f6ab3c81
51 rdf:rest rdf:nil
52 N8aba29713531407db1bb356a4d7c00a9 schema:name readcube_id
53 schema:value 5e7cc66c5ceb4d19ad7edd196ef2425d78ac05bf9105cdce9c7353920023d3b9
54 rdf:type schema:PropertyValue
55 Na1ee2efd76284988b50e033d84b0f7df rdf:first sg:person.016412363334.05
56 rdf:rest Nac605bea3fe6408887bd7d9ac3670744
57 Nabb59204e6fe428e8cf173988d0fc89c schema:name National Institute of Management Calcutta, 700027 Alipore, Calcutta, India
58 rdf:type schema:Organization
59 Nac605bea3fe6408887bd7d9ac3670744 rdf:first sg:person.016102452535.25
60 rdf:rest rdf:nil
61 Nbafaac12f4254b1b837ea82dc3c83e66 rdf:first sg:person.011633466625.33
62 rdf:rest Na1ee2efd76284988b50e033d84b0f7df
63 Nc5b2cc1dcb10467da8d5a22a06c5e11e schema:familyName Prasanna
64 schema:givenName Viktor K.
65 rdf:type schema:Person
66 Ncffa1d935ecc48a7b606b8e7aa145170 rdf:first Nc5b2cc1dcb10467da8d5a22a06c5e11e
67 rdf:rest N7fd6a59fe82b4546b96c043357b023dc
68 Ne317837cdcf44249bf445e1a0d363a53 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Neee9d6ff410e4727bb84a5d2d2102d43 schema:familyName Sahni
71 schema:givenName Sartaj
72 rdf:type schema:Person
73 Nefadfa32b0034c64a9bd050c3eab20a7 schema:name doi
74 schema:value 10.1007/3-540-36265-7_29
75 rdf:type schema:PropertyValue
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 Nabb59204e6fe428e8cf173988d0fc89c
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)


...