Approximating Covering and Minimum Enclosing Balls in Hyperbolic Geometry View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015

AUTHORS

Frank Nielsen , Gaëtan Hadjeres

ABSTRACT

We generalize the \(O(\frac{dn}{\epsilon ^2})\)-time \((1+\epsilon )\)-approximation algorithm for the smallest enclosing Euclidean ball [2, 10] to point sets in hyperbolic geometry of arbitrary dimension. We guarantee a \(O\left( 1/\epsilon ^2\right) \) convergence time by using a closed-form formula to compute the geodesic \(\alpha \)-midpoint between any two points. Those results allow us to apply the hyperbolic k-center clustering for statistical location-scale families or for multivariate spherical normal distributions by using their Fisher information matrix as the underlying Riemannian hyperbolic metric. More... »

PAGES

586-594

References to SciGraph publications

  • 1994. Foundations of Hyperbolic Manifolds in NONE
  • 2005. Fitting the Smallest Enclosing Bregman Ball in MACHINE LEARNING: ECML 2005
  • Book

    TITLE

    Geometric Science of Information

    ISBN

    978-3-319-25039-7
    978-3-319-25040-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-25040-3_63

    DOI

    http://dx.doi.org/10.1007/978-3-319-25040-3_63

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique", 
              "id": "https://www.grid.ac/institutes/grid.10877.39", 
              "name": [
                "\u00c9cole Polytechnique"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nielsen", 
            "givenName": "Frank", 
            "id": "sg:person.012062051333.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012062051333.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sony Computer Science Laboratories", 
              "id": "https://www.grid.ac/institutes/grid.452725.3", 
              "name": [
                "Sony Computer Science Laboratories"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hadjeres", 
            "givenName": "Ga\u00ebtan", 
            "id": "sg:person.07400372013.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07400372013.29"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/996546.996548", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002014382"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.comgeo.2007.04.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014198899"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11564096_65", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019847900", 
              "https://doi.org/10.1007/11564096_65"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11564096_65", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019847900", 
              "https://doi.org/10.1007/11564096_65"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-4013-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031000790", 
              "https://doi.org/10.1007/978-1-4757-4013-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-4013-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031000790", 
              "https://doi.org/10.1007/978-1-4757-4013-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.comgeo.2012.04.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034028340"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/304893.304988", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040015658"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/isvd.2010.13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093779126"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/iccsa.2010.37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094292450"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015", 
        "datePublishedReg": "2015-01-01", 
        "description": "We generalize the \\(O(\\frac{dn}{\\epsilon ^2})\\)-time \\((1+\\epsilon )\\)-approximation algorithm for the smallest enclosing Euclidean ball\u00a0[2, 10] to point sets in hyperbolic geometry of arbitrary dimension. We guarantee a \\(O\\left( 1/\\epsilon ^2\\right) \\) convergence time by using a closed-form formula to compute the geodesic \\(\\alpha \\)-midpoint between any two points. Those results allow us to apply the hyperbolic k-center clustering for statistical location-scale families or for multivariate spherical normal distributions by using their Fisher information matrix as the underlying Riemannian hyperbolic metric.", 
        "editor": [
          {
            "familyName": "Nielsen", 
            "givenName": "Frank", 
            "type": "Person"
          }, 
          {
            "familyName": "Barbaresco", 
            "givenName": "Fr\u00e9d\u00e9ric", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-25040-3_63", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-25039-7", 
            "978-3-319-25040-3"
          ], 
          "name": "Geometric Science of Information", 
          "type": "Book"
        }, 
        "name": "Approximating Covering and Minimum Enclosing Balls in Hyperbolic Geometry", 
        "pagination": "586-594", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-25040-3_63"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6bc6338204ca0124f6193a26747ef523ff66111f0cefdbb8e0a5c94c25da5c5e"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022621997"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-25040-3_63", 
          "https://app.dimensions.ai/details/publication/pub.1022621997"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T21:01", 
        "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_8690_00000257.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-25040-3_63"
      }
    ]
     

    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/978-3-319-25040-3_63'

    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/978-3-319-25040-3_63'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-25040-3_63'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-25040-3_63'


     

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

    106 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-25040-3_63 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N811e9610b5844e6caae0d58e5d62735e
    4 schema:citation sg:pub.10.1007/11564096_65
    5 sg:pub.10.1007/978-1-4757-4013-4
    6 https://doi.org/10.1016/j.comgeo.2007.04.002
    7 https://doi.org/10.1016/j.comgeo.2012.04.007
    8 https://doi.org/10.1109/iccsa.2010.37
    9 https://doi.org/10.1109/isvd.2010.13
    10 https://doi.org/10.1145/304893.304988
    11 https://doi.org/10.1145/996546.996548
    12 schema:datePublished 2015
    13 schema:datePublishedReg 2015-01-01
    14 schema:description We generalize the \(O(\frac{dn}{\epsilon ^2})\)-time \((1+\epsilon )\)-approximation algorithm for the smallest enclosing Euclidean ball [2, 10] to point sets in hyperbolic geometry of arbitrary dimension. We guarantee a \(O\left( 1/\epsilon ^2\right) \) convergence time by using a closed-form formula to compute the geodesic \(\alpha \)-midpoint between any two points. Those results allow us to apply the hyperbolic k-center clustering for statistical location-scale families or for multivariate spherical normal distributions by using their Fisher information matrix as the underlying Riemannian hyperbolic metric.
    15 schema:editor Ne4ef2858b4284c71a8d79e52dfca78bb
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N84fc67021df3428ea5d1833422fc7232
    20 schema:name Approximating Covering and Minimum Enclosing Balls in Hyperbolic Geometry
    21 schema:pagination 586-594
    22 schema:productId N338231e5eeeb44038b20ca84320e9aaf
    23 N4a20bbab1d534feb881ffb529c4a86cd
    24 Nacf525726faa4f51a171ed76574b0906
    25 schema:publisher Ne582c841e43341d0ab1c8266fe5577cc
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022621997
    27 https://doi.org/10.1007/978-3-319-25040-3_63
    28 schema:sdDatePublished 2019-04-15T21:01
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N122902b2c8b74e1f8306fc9d8765e51d
    31 schema:url http://link.springer.com/10.1007/978-3-319-25040-3_63
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N0fbcf00c78d1459dbeeeddb85244a6e9 schema:familyName Barbaresco
    36 schema:givenName Frédéric
    37 rdf:type schema:Person
    38 N122902b2c8b74e1f8306fc9d8765e51d schema:name Springer Nature - SN SciGraph project
    39 rdf:type schema:Organization
    40 N338231e5eeeb44038b20ca84320e9aaf schema:name doi
    41 schema:value 10.1007/978-3-319-25040-3_63
    42 rdf:type schema:PropertyValue
    43 N4a20bbab1d534feb881ffb529c4a86cd schema:name dimensions_id
    44 schema:value pub.1022621997
    45 rdf:type schema:PropertyValue
    46 N77bdb41dd5a343d4a2fa82402603797a rdf:first N0fbcf00c78d1459dbeeeddb85244a6e9
    47 rdf:rest rdf:nil
    48 N811e9610b5844e6caae0d58e5d62735e rdf:first sg:person.012062051333.43
    49 rdf:rest Nbfba8524879743e5b5d43d21862a9031
    50 N84fc67021df3428ea5d1833422fc7232 schema:isbn 978-3-319-25039-7
    51 978-3-319-25040-3
    52 schema:name Geometric Science of Information
    53 rdf:type schema:Book
    54 Nacf525726faa4f51a171ed76574b0906 schema:name readcube_id
    55 schema:value 6bc6338204ca0124f6193a26747ef523ff66111f0cefdbb8e0a5c94c25da5c5e
    56 rdf:type schema:PropertyValue
    57 Nbfba8524879743e5b5d43d21862a9031 rdf:first sg:person.07400372013.29
    58 rdf:rest rdf:nil
    59 Ndc78e3f5a6ee4191a96e0e5b2298aa34 schema:familyName Nielsen
    60 schema:givenName Frank
    61 rdf:type schema:Person
    62 Ne4ef2858b4284c71a8d79e52dfca78bb rdf:first Ndc78e3f5a6ee4191a96e0e5b2298aa34
    63 rdf:rest N77bdb41dd5a343d4a2fa82402603797a
    64 Ne582c841e43341d0ab1c8266fe5577cc schema:location Cham
    65 schema:name Springer International Publishing
    66 rdf:type schema:Organisation
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Statistics
    72 rdf:type schema:DefinedTerm
    73 sg:person.012062051333.43 schema:affiliation https://www.grid.ac/institutes/grid.10877.39
    74 schema:familyName Nielsen
    75 schema:givenName Frank
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012062051333.43
    77 rdf:type schema:Person
    78 sg:person.07400372013.29 schema:affiliation https://www.grid.ac/institutes/grid.452725.3
    79 schema:familyName Hadjeres
    80 schema:givenName Gaëtan
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07400372013.29
    82 rdf:type schema:Person
    83 sg:pub.10.1007/11564096_65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019847900
    84 https://doi.org/10.1007/11564096_65
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/978-1-4757-4013-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031000790
    87 https://doi.org/10.1007/978-1-4757-4013-4
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/j.comgeo.2007.04.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014198899
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/j.comgeo.2012.04.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034028340
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1109/iccsa.2010.37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094292450
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1109/isvd.2010.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093779126
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/304893.304988 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040015658
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/996546.996548 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002014382
    100 rdf:type schema:CreativeWork
    101 https://www.grid.ac/institutes/grid.10877.39 schema:alternateName École Polytechnique
    102 schema:name École Polytechnique
    103 rdf:type schema:Organization
    104 https://www.grid.ac/institutes/grid.452725.3 schema:alternateName Sony Computer Science Laboratories
    105 schema:name Sony Computer Science Laboratories
    106 rdf:type schema:Organization
     




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


    ...