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/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/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/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/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-11-24T20:55", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_509.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 Na60a9c5d2553427f8eb8b5a338c55b66
    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 N0e2b0bf1da764f6eba056db8ef60cf19
    15 Nfd3dba7b7d2c4e9a8cd63a5d2e8c9d4d
    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 N16582db010214f259ee2c5aa67172f4f
    62 N18cd39d0f9e84c38b9b214a0f4f07007
    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-11-24T20:55
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher Nc401cb92f6ff40d59a0b7bfc2527755e
    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 N0e2b0bf1da764f6eba056db8ef60cf19 schema:issueNumber 1
    73 rdf:type schema:PublicationIssue
    74 N16582db010214f259ee2c5aa67172f4f schema:name doi
    75 schema:value 10.1007/s11786-010-0042-5
    76 rdf:type schema:PropertyValue
    77 N18cd39d0f9e84c38b9b214a0f4f07007 schema:name dimensions_id
    78 schema:value pub.1002860213
    79 rdf:type schema:PropertyValue
    80 N1cb8dbbf884b472e81bd55ebe2adfe22 rdf:first sg:person.010657630057.41
    81 rdf:rest rdf:nil
    82 N5c1a78ad0c95481f9a4cc9070b957c25 rdf:first sg:person.011757371347.43
    83 rdf:rest N1cb8dbbf884b472e81bd55ebe2adfe22
    84 N87e9cf415b92431fbbc043e005a70b18 rdf:first sg:person.011005576423.77
    85 rdf:rest N5c1a78ad0c95481f9a4cc9070b957c25
    86 N8d7ff4e456a0437899184b3692f82b74 rdf:first sg:person.012066261765.49
    87 rdf:rest N87e9cf415b92431fbbc043e005a70b18
    88 Na60a9c5d2553427f8eb8b5a338c55b66 rdf:first sg:person.010445216227.89
    89 rdf:rest N8d7ff4e456a0437899184b3692f82b74
    90 Nc401cb92f6ff40d59a0b7bfc2527755e schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 Nfd3dba7b7d2c4e9a8cd63a5d2e8c9d4d schema:volumeNumber 4
    93 rdf:type schema:PublicationVolume
    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)


    ...