AnO(N logN) minimal spanning tree algorithm forN points in the plane View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-03

AUTHORS

R. C. Chang, R. C. T. Lee

ABSTRACT

We shall present a divide-and-conquer algorithm to construct minimal spanning trees out of a set of points in two dimensions. This algorithm is based upon the concept of Voronoi diagrams. If implemented in parallel, its time complexity isO(N) and it requiresO(logN) processors whereN is the number of input points.

PAGES

7-16

References to SciGraph publications

  • 1981-03. Finding minimal spanning trees in a euclidean coordinate space in BIT NUMERICAL MATHEMATICS
  • 1983-03. On the worst case of a minimal spanning tree algorithm for euclidean space in BIT NUMERICAL MATHEMATICS
  • 1980-06. Two algorithms for constructing a Delaunay triangulation in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Academia Sinica, Taipei, Taiwan, Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.28665.3f", 
              "name": [
                "National Chiao Tung University, Hsinchu, Taiwan, Republic of China", 
                "National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
                "Academia Sinica, Taipei, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "R. C.", 
            "id": "sg:person.012355347703.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Academia Sinica, Taipei, Taiwan, Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.28665.3f", 
              "name": [
                "National Chiao Tung University, Hsinchu, Taiwan, Republic of China", 
                "National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
                "Academia Sinica, Taipei, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lee", 
            "givenName": "R. C. T.", 
            "id": "sg:person.07540250215.50", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01934070", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000098792", 
              "https://doi.org/10.1007/bf01934070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01937321", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005145118", 
              "https://doi.org/10.1007/bf01937321"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00977785", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033159860", 
              "https://doi.org/10.1007/bf00977785"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1986-03", 
        "datePublishedReg": "1986-03-01", 
        "description": "We shall present a divide-and-conquer algorithm to construct minimal spanning trees out of a set of points in two dimensions. This algorithm is based upon the concept of Voronoi diagrams. If implemented in parallel, its time complexity isO(N) and it requiresO(logN) processors whereN is the number of input points.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01939358", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136252", 
            "issn": [
              "0006-3835", 
              "1572-9125"
            ], 
            "name": "BIT Numerical Mathematics", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "26"
          }
        ], 
        "keywords": [
          "trees", 
          "number", 
          "parallel", 
          "complexity", 
          "set", 
          "point", 
          "minimal spanning tree", 
          "spanning tree", 
          "divide", 
          "concept", 
          "dimensions", 
          "algorithm", 
          "diagram", 
          "plane", 
          "Voronoi diagram", 
          "time complexity", 
          "set of points", 
          "conquer algorithm", 
          "input points", 
          "wheren", 
          "processors whereN", 
          "tree algorithm forN points", 
          "algorithm forN points", 
          "forN points"
        ], 
        "name": "AnO(N logN) minimal spanning tree algorithm forN points in the plane", 
        "pagination": "7-16", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1039988459"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01939358"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01939358", 
          "https://app.dimensions.ai/details/publication/pub.1039988459"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:06", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_215.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01939358"
      }
    ]
     

    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/bf01939358'

    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/bf01939358'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    107 TRIPLES      22 PREDICATES      54 URIs      42 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01939358 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:0103
    4 schema:author N4c0e821214d847a493591938960e32f7
    5 schema:citation sg:pub.10.1007/bf00977785
    6 sg:pub.10.1007/bf01934070
    7 sg:pub.10.1007/bf01937321
    8 schema:datePublished 1986-03
    9 schema:datePublishedReg 1986-03-01
    10 schema:description We shall present a divide-and-conquer algorithm to construct minimal spanning trees out of a set of points in two dimensions. This algorithm is based upon the concept of Voronoi diagrams. If implemented in parallel, its time complexity isO(N) and it requiresO(logN) processors whereN is the number of input points.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N0a87a948338641c0bbe450fa00f84a26
    15 N161c39ea792344edb00d766805cc29ce
    16 sg:journal.1136252
    17 schema:keywords Voronoi diagram
    18 algorithm
    19 algorithm forN points
    20 complexity
    21 concept
    22 conquer algorithm
    23 diagram
    24 dimensions
    25 divide
    26 forN points
    27 input points
    28 minimal spanning tree
    29 number
    30 parallel
    31 plane
    32 point
    33 processors whereN
    34 set
    35 set of points
    36 spanning tree
    37 time complexity
    38 tree algorithm forN points
    39 trees
    40 wheren
    41 schema:name AnO(N logN) minimal spanning tree algorithm forN points in the plane
    42 schema:pagination 7-16
    43 schema:productId N9a075cc36f2f4eceb95c4749d596bd0a
    44 Ne2672daead5f4ab7a3f444a3a6e44b10
    45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039988459
    46 https://doi.org/10.1007/bf01939358
    47 schema:sdDatePublished 2021-12-01T19:06
    48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    49 schema:sdPublisher Na4526e37e36142a28858a19be2122825
    50 schema:url https://doi.org/10.1007/bf01939358
    51 sgo:license sg:explorer/license/
    52 sgo:sdDataset articles
    53 rdf:type schema:ScholarlyArticle
    54 N0a87a948338641c0bbe450fa00f84a26 schema:volumeNumber 26
    55 rdf:type schema:PublicationVolume
    56 N161c39ea792344edb00d766805cc29ce schema:issueNumber 1
    57 rdf:type schema:PublicationIssue
    58 N4c0e821214d847a493591938960e32f7 rdf:first sg:person.012355347703.02
    59 rdf:rest Nbbb48c8eded4462180288061b17bd7d5
    60 N9a075cc36f2f4eceb95c4749d596bd0a schema:name doi
    61 schema:value 10.1007/bf01939358
    62 rdf:type schema:PropertyValue
    63 Na4526e37e36142a28858a19be2122825 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nbbb48c8eded4462180288061b17bd7d5 rdf:first sg:person.07540250215.50
    66 rdf:rest rdf:nil
    67 Ne2672daead5f4ab7a3f444a3a6e44b10 schema:name dimensions_id
    68 schema:value pub.1039988459
    69 rdf:type schema:PropertyValue
    70 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Mathematical Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Applied Mathematics
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Numerical and Computational Mathematics
    78 rdf:type schema:DefinedTerm
    79 sg:journal.1136252 schema:issn 0006-3835
    80 1572-9125
    81 schema:name BIT Numerical Mathematics
    82 schema:publisher Springer Nature
    83 rdf:type schema:Periodical
    84 sg:person.012355347703.02 schema:affiliation grid-institutes:grid.28665.3f
    85 schema:familyName Chang
    86 schema:givenName R. C.
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02
    88 rdf:type schema:Person
    89 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.28665.3f
    90 schema:familyName Lee
    91 schema:givenName R. C. T.
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
    93 rdf:type schema:Person
    94 sg:pub.10.1007/bf00977785 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033159860
    95 https://doi.org/10.1007/bf00977785
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/bf01934070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000098792
    98 https://doi.org/10.1007/bf01934070
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf01937321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005145118
    101 https://doi.org/10.1007/bf01937321
    102 rdf:type schema:CreativeWork
    103 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Taipei, Taiwan, Republic of China
    104 schema:name Academia Sinica, Taipei, Taiwan, Republic of China
    105 National Chiao Tung University, Hsinchu, Taiwan, Republic of China
    106 National Tsing Hua University, Hsinchu, Taiwan, Republic of China
    107 rdf:type schema:Organization
     




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


    ...