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 Nc0f2c642d6d942c29ddeeb26903bff6d
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 N422f26ee519d43728725aaa5737a207d
17 Ndc8bc5343905452ab10deac1f1627c2a
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 N56d16eb8017a4037a48d89f201cf10b2
22 Naf08310f665240f0ae6b29502b65c7f4
23 Ndd55674ded0443008d5af084b0002d5a
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 N4801e37d210943adba1ccdbf0baee257
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 N422f26ee519d43728725aaa5737a207d schema:issueNumber 1-6
34 rdf:type schema:PublicationIssue
35 N4801e37d210943adba1ccdbf0baee257 schema:name Springer Nature - SN SciGraph project
36 rdf:type schema:Organization
37 N56d16eb8017a4037a48d89f201cf10b2 schema:name dimensions_id
38 schema:value pub.1036591041
39 rdf:type schema:PropertyValue
40 Naf08310f665240f0ae6b29502b65c7f4 schema:name doi
41 schema:value 10.1007/bf01758842
42 rdf:type schema:PropertyValue
43 Nc0f2c642d6d942c29ddeeb26903bff6d rdf:first sg:person.013174232477.45
44 rdf:rest Ncc4b02c648b54973b48a94119bd22663
45 Ncc4b02c648b54973b48a94119bd22663 rdf:first sg:person.01312526135.27
46 rdf:rest Nefda60f861b447638a9df9f61e4409e0
47 Ndc8bc5343905452ab10deac1f1627c2a schema:volumeNumber 8
48 rdf:type schema:PublicationVolume
49 Ndd55674ded0443008d5af084b0002d5a schema:name readcube_id
50 schema:value ae4e49e1e25feb22f7a424ca25759580a5617d1da5b4f54ef40738c43f634130
51 rdf:type schema:PropertyValue
52 Nefda60f861b447638a9df9f61e4409e0 rdf:first sg:person.07540250215.50
53 rdf:rest rdf:nil
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)


...