Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1992-12

AUTHORS

M. S. Chang, C. Y. Tang, R. C. T. Lee

ABSTRACT

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,Erk) whereErk is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofEr17. We also prove that ¦Erk¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n1.5 log0.5n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n2 +n1.5 log0.5n). More... »

PAGES

177-194

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": {
          "alternateName": "National Chung Cheng University", 
          "id": "https://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Institute of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "M. S.", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Institute of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "C. Y.", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Academia Sinica", 
          "id": "https://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "National Tsing Hua University, Hsinchu, Taiwan", 
            "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": "https://doi.org/10.1016/0196-6774(88)90031-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011683516"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1024857777", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-51576-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857777", 
          "https://doi.org/10.1007/978-3-642-51576-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-51576-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857777", 
          "https://doi.org/10.1007/978-3-642-51576-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(80)90066-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025755637"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(80)90066-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025755637"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(86)90012-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051989920"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(86)90012-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051989920"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1985.3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086208008"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992-12", 
    "datePublishedReg": "1992-12-01", 
    "description": "Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,Erk) whereErk is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofEr17. We also prove that \u00a6Erk\u00a6 < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n1.5 log0.5n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n2 +n1.5 log0.5n).", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01758842", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-6", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "8"
      }
    ], 
    "name": "Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs", 
    "pagination": "177-194", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ae4e49e1e25feb22f7a424ca25759580a5617d1da5b4f54ef40738c43f634130"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01758842"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036591041"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01758842", 
      "https://app.dimensions.ai/details/publication/pub.1036591041"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T09:53", 
    "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/0000000347_0000000347/records_89793_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01758842"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

100 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01758842 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N0cc939fa920c43a7af0d166670a69f63
4 schema:citation sg:pub.10.1007/978-3-642-51576-7
5 https://app.dimensions.ai/details/publication/pub.1024857777
6 https://doi.org/10.1016/0031-3203(80)90066-7
7 https://doi.org/10.1016/0031-3203(86)90012-9
8 https://doi.org/10.1016/0196-6774(88)90031-4
9 https://doi.org/10.1109/sfcs.1985.3
10 schema:datePublished 1992-12
11 schema:datePublishedReg 1992-12-01
12 schema:description Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,Erk) whereErk is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofEr17. We also prove that ¦Erk¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n1.5 log0.5n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n2 +n1.5 log0.5n).
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N9cdf645f2d6e43e5a2a6c7bdc97cbaca
17 Nbfd39645055a42828722a76cb7334e91
18 sg:journal.1047644
19 schema:name Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs
20 schema:pagination 177-194
21 schema:productId N18df36cc4d0a408f8d0705f2fb1b07b3
22 N8829228c816a4308ad4d271a32c71770
23 Nb0e510e35c6646dd854c1e0b576a2c2d
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036591041
25 https://doi.org/10.1007/bf01758842
26 schema:sdDatePublished 2019-04-11T09:53
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N26388623d7664d519eeeebb11d067132
29 schema:url http://link.springer.com/10.1007/BF01758842
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N0cc939fa920c43a7af0d166670a69f63 rdf:first sg:person.013174232477.45
34 rdf:rest N49aca198dd4d4e8eb56b74dc4a057e09
35 N18df36cc4d0a408f8d0705f2fb1b07b3 schema:name dimensions_id
36 schema:value pub.1036591041
37 rdf:type schema:PropertyValue
38 N26388623d7664d519eeeebb11d067132 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N45614c7a341d4b66bde3e5d7eb9505da rdf:first sg:person.07540250215.50
41 rdf:rest rdf:nil
42 N49aca198dd4d4e8eb56b74dc4a057e09 rdf:first sg:person.01312526135.27
43 rdf:rest N45614c7a341d4b66bde3e5d7eb9505da
44 N8829228c816a4308ad4d271a32c71770 schema:name doi
45 schema:value 10.1007/bf01758842
46 rdf:type schema:PropertyValue
47 N9cdf645f2d6e43e5a2a6c7bdc97cbaca schema:volumeNumber 8
48 rdf:type schema:PublicationVolume
49 Nb0e510e35c6646dd854c1e0b576a2c2d schema:name readcube_id
50 schema:value ae4e49e1e25feb22f7a424ca25759580a5617d1da5b4f54ef40738c43f634130
51 rdf:type schema:PropertyValue
52 Nbfd39645055a42828722a76cb7334e91 schema:issueNumber 1-6
53 rdf:type schema:PublicationIssue
54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
55 schema:name Information and Computing Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
58 schema:name Computation Theory and Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1047644 schema:issn 0178-4617
61 1432-0541
62 schema:name Algorithmica
63 rdf:type schema:Periodical
64 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
65 schema:familyName Tang
66 schema:givenName C. Y.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
68 rdf:type schema:Person
69 sg:person.013174232477.45 schema:affiliation https://www.grid.ac/institutes/grid.412047.4
70 schema:familyName Chang
71 schema:givenName M. S.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
73 rdf:type schema:Person
74 sg:person.07540250215.50 schema:affiliation https://www.grid.ac/institutes/grid.28665.3f
75 schema:familyName Lee
76 schema:givenName R. C. T.
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
78 rdf:type schema:Person
79 sg:pub.10.1007/978-3-642-51576-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024857777
80 https://doi.org/10.1007/978-3-642-51576-7
81 rdf:type schema:CreativeWork
82 https://app.dimensions.ai/details/publication/pub.1024857777 schema:CreativeWork
83 https://doi.org/10.1016/0031-3203(80)90066-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025755637
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0031-3203(86)90012-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051989920
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/0196-6774(88)90031-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011683516
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1109/sfcs.1985.3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086208008
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.28665.3f schema:alternateName Academia Sinica
92 schema:name Academia Sinica, Taipei, Taiwan, Republic of China
93 National Tsing Hua University, Hsinchu, Taiwan
94 rdf:type schema:Organization
95 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
96 schema:name Institute of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, Republic of China
97 rdf:type schema:Organization
98 https://www.grid.ac/institutes/grid.412047.4 schema:alternateName National Chung Cheng University
99 schema:name Institute of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan, Republic of China
100 rdf:type schema:Organization
 




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


...