Arrangements on Parametric Surfaces I: General Framework and Infrastructure View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-10-16

AUTHORS

Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein

ABSTRACT

We introduce a framework for the construction, maintenance, and manipulation of arrangements of curves embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The framework applies to planes, cylinders, spheres, tori, and surfaces homeomorphic to them. We reduce the effort needed to generalize existing algorithms, such as the sweep line and zone traversal algorithms, originally designed for arrangements of bounded curves in the plane, by extensive reuse of code. We have realized our approach as the Cgal package Arrangement_on_surface_2. We define a compact and modular interface for our framework; for a given application a required small subset of the interface can be identified. Then, only this subset must be implemented. A companion paper describes concretizations for several types of surfaces and curves embedded on them, and applications. This is the first implementation of a generic algorithm that can handle arrangements on a large class of parametric surfaces. More... »

PAGES

45-66

References to SciGraph publications

  • 2006-01-01. Arrangements in EFFECTIVE COMPUTATIONAL GEOMETRY FOR CURVES AND SURFACES
  • 1986-03-01. Voronoi diagrams and arrangements in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2010-10-13. Arrangements on Parametric Surfaces II: Concretizations and Applications in MATHEMATICS IN COMPUTER SCIENCE
  • 2006. Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces in ALGORITHMS – ESA 2006
  • 2007-01-01. Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step in ALGORITHMS – ESA 2007
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11786-010-0042-5

    DOI

    http://dx.doi.org/10.1007/s11786-010-0042-5

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Berberich", 
            "givenName": "Eric", 
            "id": "sg:person.010445216227.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445216227.89"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fogel", 
            "givenName": "Efi", 
            "id": "sg:person.012066261765.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012066261765.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Halperin", 
            "givenName": "Dan", 
            "id": "sg:person.011005576423.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011005576423.77"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
              "id": "http://www.grid.ac/institutes/grid.419528.3", 
              "name": [
                "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mehlhorn", 
            "givenName": "Kurt", 
            "id": "sg:person.011757371347.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wein", 
            "givenName": "Ron", 
            "id": "sg:person.010657630057.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010657630057.41"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-75520-3_57", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035922877", 
              "https://doi.org/10.1007/978-3-540-75520-3_57"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11786-010-0043-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017964768", 
              "https://doi.org/10.1007/s11786-010-0043-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187681", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015637565", 
              "https://doi.org/10.1007/bf02187681"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11841036_70", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052293315", 
              "https://doi.org/10.1007/11841036_70"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-33259-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011398558", 
              "https://doi.org/10.1007/978-3-540-33259-6_1"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-10-16", 
        "datePublishedReg": "2010-10-16", 
        "description": "We introduce a framework for the construction, maintenance, and manipulation of arrangements of curves embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The framework applies to planes, cylinders, spheres, tori, and surfaces homeomorphic to them. We reduce the effort needed to generalize existing algorithms, such as the sweep line and zone traversal algorithms, originally designed for arrangements of bounded curves in the plane, by extensive reuse of code. We have realized our approach as the Cgal package Arrangement_on_surface_2. We define a compact and modular interface for our framework; for a given application a required small subset of the interface can be identified. Then, only this subset must be implemented. A companion paper describes concretizations for several types of surfaces and curves embedded on them, and applications. This is the first implementation of a generic algorithm that can handle arrangements on a large class of parametric surfaces.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11786-010-0042-5", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136594", 
            "issn": [
              "1661-8270", 
              "1661-8289"
            ], 
            "name": "Mathematics in Computer Science", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "4"
          }
        ], 
        "keywords": [
          "parametric surfaces", 
          "three-dimensional space", 
          "large class", 
          "general framework", 
          "sweep line", 
          "generic algorithm", 
          "companion paper", 
          "algorithm", 
          "traversal algorithm", 
          "torus", 
          "plane", 
          "extensive reuse", 
          "framework", 
          "first implementation", 
          "surface I", 
          "small subset", 
          "space", 
          "applications", 
          "curves", 
          "types of surfaces", 
          "class", 
          "cylinder", 
          "package", 
          "subset", 
          "sphere", 
          "code", 
          "surface", 
          "approach", 
          "construction", 
          "implementation", 
          "arrangement", 
          "modular interface", 
          "interface", 
          "lines", 
          "types", 
          "concretization", 
          "manipulation", 
          "efforts", 
          "infrastructure", 
          "reuse", 
          "maintenance", 
          "paper"
        ], 
        "name": "Arrangements on Parametric Surfaces I: General Framework and Infrastructure", 
        "pagination": "45-66", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1002860213"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11786-010-0042-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11786-010-0042-5", 
          "https://app.dimensions.ai/details/publication/pub.1002860213"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:36", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_522.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11786-010-0042-5"
      }
    ]
     

    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/s11786-010-0042-5'

    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/s11786-010-0042-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11786-010-0042-5'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11786-010-0042-5'


     

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

    150 TRIPLES      21 PREDICATES      71 URIs      58 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11786-010-0042-5 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N9586f7260028431fbd04bded3d0aedab
    4 schema:citation sg:pub.10.1007/11841036_70
    5 sg:pub.10.1007/978-3-540-33259-6_1
    6 sg:pub.10.1007/978-3-540-75520-3_57
    7 sg:pub.10.1007/bf02187681
    8 sg:pub.10.1007/s11786-010-0043-4
    9 schema:datePublished 2010-10-16
    10 schema:datePublishedReg 2010-10-16
    11 schema:description We introduce a framework for the construction, maintenance, and manipulation of arrangements of curves embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The framework applies to planes, cylinders, spheres, tori, and surfaces homeomorphic to them. We reduce the effort needed to generalize existing algorithms, such as the sweep line and zone traversal algorithms, originally designed for arrangements of bounded curves in the plane, by extensive reuse of code. We have realized our approach as the Cgal package Arrangement_on_surface_2. We define a compact and modular interface for our framework; for a given application a required small subset of the interface can be identified. Then, only this subset must be implemented. A companion paper describes concretizations for several types of surfaces and curves embedded on them, and applications. This is the first implementation of a generic algorithm that can handle arrangements on a large class of parametric surfaces.
    12 schema:genre article
    13 schema:isAccessibleForFree true
    14 schema:isPartOf N6a909f71e0fa4b56b46be7529f0521a1
    15 N7d8e219f16df40bea1dfc4f0f0c30539
    16 sg:journal.1136594
    17 schema:keywords algorithm
    18 applications
    19 approach
    20 arrangement
    21 class
    22 code
    23 companion paper
    24 concretization
    25 construction
    26 curves
    27 cylinder
    28 efforts
    29 extensive reuse
    30 first implementation
    31 framework
    32 general framework
    33 generic algorithm
    34 implementation
    35 infrastructure
    36 interface
    37 large class
    38 lines
    39 maintenance
    40 manipulation
    41 modular interface
    42 package
    43 paper
    44 parametric surfaces
    45 plane
    46 reuse
    47 small subset
    48 space
    49 sphere
    50 subset
    51 surface
    52 surface I
    53 sweep line
    54 three-dimensional space
    55 torus
    56 traversal algorithm
    57 types
    58 types of surfaces
    59 schema:name Arrangements on Parametric Surfaces I: General Framework and Infrastructure
    60 schema:pagination 45-66
    61 schema:productId Nd0b307ddbb2b4fb18acc7a1433d9e6af
    62 Nff9c09bea0ff4f1591591a2e35772c6b
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002860213
    64 https://doi.org/10.1007/s11786-010-0042-5
    65 schema:sdDatePublished 2022-10-01T06:36
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher N64f38fb56cbd429397469732eb1097a0
    68 schema:url https://doi.org/10.1007/s11786-010-0042-5
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N57e10536eb444ac399f8e8e19e48fd1c rdf:first sg:person.010657630057.41
    73 rdf:rest rdf:nil
    74 N64f38fb56cbd429397469732eb1097a0 schema:name Springer Nature - SN SciGraph project
    75 rdf:type schema:Organization
    76 N6a909f71e0fa4b56b46be7529f0521a1 schema:issueNumber 1
    77 rdf:type schema:PublicationIssue
    78 N6c8f15566884473ebfc62cc15d7bc0ee rdf:first sg:person.011757371347.43
    79 rdf:rest N57e10536eb444ac399f8e8e19e48fd1c
    80 N7d8e219f16df40bea1dfc4f0f0c30539 schema:volumeNumber 4
    81 rdf:type schema:PublicationVolume
    82 N9586f7260028431fbd04bded3d0aedab rdf:first sg:person.010445216227.89
    83 rdf:rest N968250d5deca4d718cf5b2c74e3b448e
    84 N968250d5deca4d718cf5b2c74e3b448e rdf:first sg:person.012066261765.49
    85 rdf:rest Nd4d866e5c4b145a6864d6455e2a51384
    86 Nd0b307ddbb2b4fb18acc7a1433d9e6af schema:name dimensions_id
    87 schema:value pub.1002860213
    88 rdf:type schema:PropertyValue
    89 Nd4d866e5c4b145a6864d6455e2a51384 rdf:first sg:person.011005576423.77
    90 rdf:rest N6c8f15566884473ebfc62cc15d7bc0ee
    91 Nff9c09bea0ff4f1591591a2e35772c6b schema:name doi
    92 schema:value 10.1007/s11786-010-0042-5
    93 rdf:type schema:PropertyValue
    94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information and Computing Sciences
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Artificial Intelligence and Image Processing
    99 rdf:type schema:DefinedTerm
    100 sg:journal.1136594 schema:issn 1661-8270
    101 1661-8289
    102 schema:name Mathematics in Computer Science
    103 schema:publisher Springer Nature
    104 rdf:type schema:Periodical
    105 sg:person.010445216227.89 schema:affiliation grid-institutes:grid.12136.37
    106 schema:familyName Berberich
    107 schema:givenName Eric
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445216227.89
    109 rdf:type schema:Person
    110 sg:person.010657630057.41 schema:affiliation grid-institutes:grid.12136.37
    111 schema:familyName Wein
    112 schema:givenName Ron
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010657630057.41
    114 rdf:type schema:Person
    115 sg:person.011005576423.77 schema:affiliation grid-institutes:grid.12136.37
    116 schema:familyName Halperin
    117 schema:givenName Dan
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011005576423.77
    119 rdf:type schema:Person
    120 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
    121 schema:familyName Mehlhorn
    122 schema:givenName Kurt
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
    124 rdf:type schema:Person
    125 sg:person.012066261765.49 schema:affiliation grid-institutes:grid.12136.37
    126 schema:familyName Fogel
    127 schema:givenName Efi
    128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012066261765.49
    129 rdf:type schema:Person
    130 sg:pub.10.1007/11841036_70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052293315
    131 https://doi.org/10.1007/11841036_70
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-540-33259-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011398558
    134 https://doi.org/10.1007/978-3-540-33259-6_1
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-540-75520-3_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035922877
    137 https://doi.org/10.1007/978-3-540-75520-3_57
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/bf02187681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637565
    140 https://doi.org/10.1007/bf02187681
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s11786-010-0043-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017964768
    143 https://doi.org/10.1007/s11786-010-0043-4
    144 rdf:type schema:CreativeWork
    145 grid-institutes:grid.12136.37 schema:alternateName School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel
    146 schema:name School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel
    147 rdf:type schema:Organization
    148 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
    149 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
    150 rdf:type schema:Organization
     




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


    ...