Efficient Algorithms for Maximum Regression Depth View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-06

AUTHORS

Marc van Kreveld, Joseph S. B. Mitchell, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann

ABSTRACT

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(nd) time and O(nd−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results. More... »

PAGES

656-677

References to SciGraph publications

  • 2001-01. Point Sets with Many k-Sets in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2003-08. The Complexity of Hyperplane Depth in the Plane in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1987. Algorithms in Combinatorial Geometry in NONE
  • 2000-03. Regression Depth and Center Points in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1998-03. Improved Bounds for Planar k -Sets and Related Problems in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1993-02. Cutting hyperplanes for divide-and-conquer in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1993-12. k-sets and random hulls in COMBINATORICA
  • 1986-03. Halfspace range search: An algorithmic application ofk-sets in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1998-08. Computing location depth and regression depth in higher dimensions in STATISTICS AND COMPUTING
  • 1999-09. Depth in an Arrangement of Hyperplanes in DISCRETE & COMPUTATIONAL GEOMETRY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00454-007-9046-6

    DOI

    http://dx.doi.org/10.1007/s00454-007-9046-6

    DIMENSIONS

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


    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": "Utrecht University", 
              "id": "https://www.grid.ac/institutes/grid.5477.1", 
              "name": [
                "Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "van Kreveld", 
            "givenName": "Marc", 
            "id": "sg:person.010602760715.18", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010602760715.18"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Stony Brook University", 
              "id": "https://www.grid.ac/institutes/grid.36425.36", 
              "name": [
                "Department of Applied Mathematics and Statistics, SUNY Stony Brook, Stony Brook, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mitchell", 
            "givenName": "Joseph S. B.", 
            "id": "sg:person.07367672553.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07367672553.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Antwerp", 
              "id": "https://www.grid.ac/institutes/grid.5284.b", 
              "name": [
                "Department of Mathematics and Computer Science, Universitaire Instelling Antwerpen, Antwerpen, Belgium"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rousseeuw", 
            "givenName": "Peter", 
            "id": "sg:person.0775337371.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0775337371.63"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tel Aviv University", 
              "id": "https://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel Aviv University, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sharir", 
            "givenName": "Micha", 
            "id": "sg:person.013672552025.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013672552025.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of North Carolina at Chapel Hill", 
              "id": "https://www.grid.ac/institutes/grid.10698.36", 
              "name": [
                "Department of Computer Science, UNC Chapel Hill, Chapel Hill, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Snoeyink", 
            "givenName": "Jack", 
            "id": "sg:person.010135275521.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010135275521.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Eindhoven University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6852.9", 
              "name": [
                "Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Speckmann", 
            "givenName": "Bettina", 
            "id": "sg:person.0725057667.81", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0725057667.81"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1201/9781420035315.ch57", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001021470"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004540010022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004316065", 
              "https://doi.org/10.1007/s004540010022"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004540010022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004316065", 
              "https://doi.org/10.1007/s004540010022"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-003-0011-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005704177", 
              "https://doi.org/10.1007/s00454-003-0011-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-003-0011-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005704177", 
              "https://doi.org/10.1007/s00454-003-0011-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/363647.363652", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008361575"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmva.2001.1997", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011168555"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmva.1999.1870", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014608331"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02189314", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020450990", 
              "https://doi.org/10.1007/bf02189314"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02189314", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020450990", 
              "https://doi.org/10.1007/bf02189314"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0925-7721(95)00020-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021052431"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0925-7721(97)00025-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023669386"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008945009397", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024868624", 
              "https://doi.org/10.1023/a:1008945009397"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009354", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027985175", 
              "https://doi.org/10.1007/pl00009354"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009354", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027985175", 
              "https://doi.org/10.1007/pl00009354"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1996.0040", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028094630"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-9473(99)00112-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028883369"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(91)90177-j", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029934668"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(85)90193-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033673935"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(85)90193-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033673935"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-9473(96)00027-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034778667"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmva.1998.1804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036092292"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009452", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038466844", 
              "https://doi.org/10.1007/pl00009452"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009452", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038466844", 
              "https://doi.org/10.1007/pl00009452"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01303520", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041059149", 
              "https://doi.org/10.1007/bf01303520"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01303520", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041059149", 
              "https://doi.org/10.1007/bf01303520"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009502", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042254573", 
              "https://doi.org/10.1007/pl00009502"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009502", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042254573", 
              "https://doi.org/10.1007/pl00009502"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmva.1998.1751", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044736952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(91)90106-r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044871636"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187685", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045338512", 
              "https://doi.org/10.1007/bf02187685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187685", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045338512", 
              "https://doi.org/10.1007/bf02187685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-61568-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049996833", 
              "https://doi.org/10.1007/978-3-642-61568-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-61568-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049996833", 
              "https://doi.org/10.1007/978-3-642-61568-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(93)90234-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052392461"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/01621459.1999.10474129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1058305578"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/01621459.1999.10474137", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1058305586"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218055", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842154"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0222031", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842434"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218195992000020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062960718"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2670163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1070052616"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008-06", 
        "datePublishedReg": "2008-06-01", 
        "description": "We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(nd) time and O(nd\u22121) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299\u2013309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00454-007-9046-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1043660", 
            "issn": [
              "0179-5376", 
              "1432-0444"
            ], 
            "name": "Discrete & Computational Geometry", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "39"
          }
        ], 
        "name": "Efficient Algorithms for Maximum Regression Depth", 
        "pagination": "656-677", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "aa1e5a6441f288f38c01f76f2a064ddad943cb1a6178e81d75d02c2d56adf9c1"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00454-007-9046-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035711932"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00454-007-9046-6", 
          "https://app.dimensions.ai/details/publication/pub.1035711932"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T01:07", 
        "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_8697_00000514.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00454-007-9046-6"
      }
    ]
     

    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/s00454-007-9046-6'

    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/s00454-007-9046-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00454-007-9046-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00454-007-9046-6'


     

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

    217 TRIPLES      21 PREDICATES      59 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00454-007-9046-6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Ne956295aae4d4aee8582e62f43519037
    4 schema:citation sg:pub.10.1007/978-3-642-61568-9
    5 sg:pub.10.1007/bf01303520
    6 sg:pub.10.1007/bf02187685
    7 sg:pub.10.1007/bf02189314
    8 sg:pub.10.1007/pl00009354
    9 sg:pub.10.1007/pl00009452
    10 sg:pub.10.1007/pl00009502
    11 sg:pub.10.1007/s00454-003-0011-x
    12 sg:pub.10.1007/s004540010022
    13 sg:pub.10.1023/a:1008945009397
    14 https://doi.org/10.1006/jagm.1996.0040
    15 https://doi.org/10.1006/jmva.1998.1751
    16 https://doi.org/10.1006/jmva.1998.1804
    17 https://doi.org/10.1006/jmva.1999.1870
    18 https://doi.org/10.1006/jmva.2001.1997
    19 https://doi.org/10.1016/0012-365x(85)90193-1
    20 https://doi.org/10.1016/0020-0190(91)90106-r
    21 https://doi.org/10.1016/0020-0190(91)90177-j
    22 https://doi.org/10.1016/0020-0190(93)90234-z
    23 https://doi.org/10.1016/0925-7721(95)00020-8
    24 https://doi.org/10.1016/s0167-9473(96)00027-8
    25 https://doi.org/10.1016/s0167-9473(99)00112-7
    26 https://doi.org/10.1016/s0925-7721(97)00025-4
    27 https://doi.org/10.1080/01621459.1999.10474129
    28 https://doi.org/10.1080/01621459.1999.10474137
    29 https://doi.org/10.1137/0215024
    30 https://doi.org/10.1137/0218055
    31 https://doi.org/10.1137/0222031
    32 https://doi.org/10.1142/s0218195992000020
    33 https://doi.org/10.1145/363647.363652
    34 https://doi.org/10.1201/9781420035315.ch57
    35 https://doi.org/10.2307/2670163
    36 schema:datePublished 2008-06
    37 schema:datePublishedReg 2008-06-01
    38 schema:description We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(nd) time and O(nd−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.
    39 schema:genre research_article
    40 schema:inLanguage en
    41 schema:isAccessibleForFree true
    42 schema:isPartOf N3d7e8935bf804c71a6bc4f59d29d6d35
    43 N7b61dbb4d3514ab8add57fca24d87bd0
    44 sg:journal.1043660
    45 schema:name Efficient Algorithms for Maximum Regression Depth
    46 schema:pagination 656-677
    47 schema:productId N3a57221db70547648d78037913217374
    48 N6699ab4fb57244b0b978ad724afe600b
    49 Nda30697488574735b53f944d4fe87204
    50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035711932
    51 https://doi.org/10.1007/s00454-007-9046-6
    52 schema:sdDatePublished 2019-04-11T01:07
    53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    54 schema:sdPublisher Ncc9d9846eff84570a423ff82ac9ca14f
    55 schema:url http://link.springer.com/10.1007%2Fs00454-007-9046-6
    56 sgo:license sg:explorer/license/
    57 sgo:sdDataset articles
    58 rdf:type schema:ScholarlyArticle
    59 N3a57221db70547648d78037913217374 schema:name readcube_id
    60 schema:value aa1e5a6441f288f38c01f76f2a064ddad943cb1a6178e81d75d02c2d56adf9c1
    61 rdf:type schema:PropertyValue
    62 N3d7e8935bf804c71a6bc4f59d29d6d35 schema:issueNumber 4
    63 rdf:type schema:PublicationIssue
    64 N6699ab4fb57244b0b978ad724afe600b schema:name doi
    65 schema:value 10.1007/s00454-007-9046-6
    66 rdf:type schema:PropertyValue
    67 N7b61dbb4d3514ab8add57fca24d87bd0 schema:volumeNumber 39
    68 rdf:type schema:PublicationVolume
    69 N92e947b7573d4463bb5abfee3b1c4ba0 rdf:first sg:person.07367672553.08
    70 rdf:rest Ne4d56a9ac40b47d08a6c10a396675cf6
    71 Nbe117eca0de94bc9bdd58a94ee33ce6e rdf:first sg:person.013672552025.49
    72 rdf:rest Nf6f6c3a804ef4d21a78f0f8490558727
    73 Ncc9d9846eff84570a423ff82ac9ca14f schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 Nd24c7bd2c5a5422eb752533fd47a575d rdf:first sg:person.0725057667.81
    76 rdf:rest rdf:nil
    77 Nda30697488574735b53f944d4fe87204 schema:name dimensions_id
    78 schema:value pub.1035711932
    79 rdf:type schema:PropertyValue
    80 Ne4d56a9ac40b47d08a6c10a396675cf6 rdf:first sg:person.0775337371.63
    81 rdf:rest Nbe117eca0de94bc9bdd58a94ee33ce6e
    82 Ne956295aae4d4aee8582e62f43519037 rdf:first sg:person.010602760715.18
    83 rdf:rest N92e947b7573d4463bb5abfee3b1c4ba0
    84 Nf6f6c3a804ef4d21a78f0f8490558727 rdf:first sg:person.010135275521.12
    85 rdf:rest Nd24c7bd2c5a5422eb752533fd47a575d
    86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Information and Computing Sciences
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Computation Theory and Mathematics
    91 rdf:type schema:DefinedTerm
    92 sg:journal.1043660 schema:issn 0179-5376
    93 1432-0444
    94 schema:name Discrete & Computational Geometry
    95 rdf:type schema:Periodical
    96 sg:person.010135275521.12 schema:affiliation https://www.grid.ac/institutes/grid.10698.36
    97 schema:familyName Snoeyink
    98 schema:givenName Jack
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010135275521.12
    100 rdf:type schema:Person
    101 sg:person.010602760715.18 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
    102 schema:familyName van Kreveld
    103 schema:givenName Marc
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010602760715.18
    105 rdf:type schema:Person
    106 sg:person.013672552025.49 schema:affiliation https://www.grid.ac/institutes/grid.12136.37
    107 schema:familyName Sharir
    108 schema:givenName Micha
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013672552025.49
    110 rdf:type schema:Person
    111 sg:person.0725057667.81 schema:affiliation https://www.grid.ac/institutes/grid.6852.9
    112 schema:familyName Speckmann
    113 schema:givenName Bettina
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0725057667.81
    115 rdf:type schema:Person
    116 sg:person.07367672553.08 schema:affiliation https://www.grid.ac/institutes/grid.36425.36
    117 schema:familyName Mitchell
    118 schema:givenName Joseph S. B.
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07367672553.08
    120 rdf:type schema:Person
    121 sg:person.0775337371.63 schema:affiliation https://www.grid.ac/institutes/grid.5284.b
    122 schema:familyName Rousseeuw
    123 schema:givenName Peter
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0775337371.63
    125 rdf:type schema:Person
    126 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
    127 https://doi.org/10.1007/978-3-642-61568-9
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf01303520 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041059149
    130 https://doi.org/10.1007/bf01303520
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf02187685 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045338512
    133 https://doi.org/10.1007/bf02187685
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bf02189314 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020450990
    136 https://doi.org/10.1007/bf02189314
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/pl00009354 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027985175
    139 https://doi.org/10.1007/pl00009354
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/pl00009452 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038466844
    142 https://doi.org/10.1007/pl00009452
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/pl00009502 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042254573
    145 https://doi.org/10.1007/pl00009502
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/s00454-003-0011-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1005704177
    148 https://doi.org/10.1007/s00454-003-0011-x
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/s004540010022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004316065
    151 https://doi.org/10.1007/s004540010022
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1023/a:1008945009397 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024868624
    154 https://doi.org/10.1023/a:1008945009397
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1006/jagm.1996.0040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028094630
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1006/jmva.1998.1751 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044736952
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1006/jmva.1998.1804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036092292
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1006/jmva.1999.1870 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014608331
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1006/jmva.2001.1997 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011168555
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/0012-365x(85)90193-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033673935
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1016/0020-0190(91)90106-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1044871636
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1016/0020-0190(91)90177-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1029934668
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1016/0020-0190(93)90234-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1052392461
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1016/0925-7721(95)00020-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021052431
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1016/s0167-9473(96)00027-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034778667
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1016/s0167-9473(99)00112-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028883369
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1016/s0925-7721(97)00025-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023669386
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1080/01621459.1999.10474129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058305578
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1080/01621459.1999.10474137 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058305586
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1137/0215024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841886
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1137/0218055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842154
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1137/0222031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842434
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1142/s0218195992000020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960718
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1145/363647.363652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008361575
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1201/9781420035315.ch57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001021470
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.2307/2670163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070052616
    199 rdf:type schema:CreativeWork
    200 https://www.grid.ac/institutes/grid.10698.36 schema:alternateName University of North Carolina at Chapel Hill
    201 schema:name Department of Computer Science, UNC Chapel Hill, Chapel Hill, USA
    202 rdf:type schema:Organization
    203 https://www.grid.ac/institutes/grid.12136.37 schema:alternateName Tel Aviv University
    204 schema:name School of Computer Science, Tel Aviv University, Tel Aviv, Israel
    205 rdf:type schema:Organization
    206 https://www.grid.ac/institutes/grid.36425.36 schema:alternateName Stony Brook University
    207 schema:name Department of Applied Mathematics and Statistics, SUNY Stony Brook, Stony Brook, USA
    208 rdf:type schema:Organization
    209 https://www.grid.ac/institutes/grid.5284.b schema:alternateName University of Antwerp
    210 schema:name Department of Mathematics and Computer Science, Universitaire Instelling Antwerpen, Antwerpen, Belgium
    211 rdf:type schema:Organization
    212 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
    213 schema:name Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
    214 rdf:type schema:Organization
    215 https://www.grid.ac/institutes/grid.6852.9 schema:alternateName Eindhoven University of Technology
    216 schema:name Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands
    217 rdf:type schema:Organization
     




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


    ...