A simplified technique for hidden-line elimination in terrains View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1992

AUTHORS

Franco P. Preparata , Jeffrey Scott Vitter

ABSTRACT

In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d+n)log2 n) time, where d is the size of the final display. While the asymptotic performance is the same as that of the previously best known algorithm, our implementation is simpler and more practical, because we try to take full advantage of the specific geometrical properties of the terrain. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O(log2 n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree. More... »

PAGES

133-146

Book

TITLE

STACS 92

ISBN

978-3-540-55210-9
978-3-540-46775-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-55210-3_179

DOI

http://dx.doi.org/10.1007/3-540-55210-3_179

DIMENSIONS

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


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": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Dept. of Computer Science, Brown University, 02912-1910\u00a0Providence, R. I., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preparata", 
        "givenName": "Franco P.", 
        "id": "sg:person.012774535455.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012774535455.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Dept. of Computer Science, Brown University, 02912-1910\u00a0Providence, R. I., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(89)90137-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017954086"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1021021236", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579170", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046501024", 
          "https://doi.org/10.1007/bf02579170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579170", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046501024", 
          "https://doi.org/10.1007/bf02579170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/78964.78967", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047786983"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(81)90012-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048640045"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d+n)log2 n) time, where d is the size of the final display. While the asymptotic performance is the same as that of the previously best known algorithm, our implementation is simpler and more practical, because we try to take full advantage of the specific geometrical properties of the terrain. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O(log2 n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree.", 
    "editor": [
      {
        "familyName": "Finkel", 
        "givenName": "Alain", 
        "type": "Person"
      }, 
      {
        "familyName": "Jantzen", 
        "givenName": "Matthias", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-55210-3_179", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3373848", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3382805", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-55210-9", 
        "978-3-540-46775-5"
      ], 
      "name": "STACS 92", 
      "type": "Book"
    }, 
    "name": "A simplified technique for hidden-line elimination in terrains", 
    "pagination": "133-146", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-55210-3_179"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ed9d8ea89d275aa27c9b827a84b790bfd71dd69d2477bffc55b8951f358f35b2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049880896"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-55210-3_179", 
      "https://app.dimensions.ai/details/publication/pub.1049880896"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T13:04", 
    "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_8663_00000557.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-55210-3_179"
  }
]
 

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/3-540-55210-3_179'

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/3-540-55210-3_179'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-55210-3_179'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-55210-3_179'


 

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

100 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-55210-3_179 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Ncc4cb5595c1f4d7886e7e3e2aaa588d8
4 schema:citation sg:pub.10.1007/978-1-4612-1098-6
5 sg:pub.10.1007/bf02579170
6 https://app.dimensions.ai/details/publication/pub.1021021236
7 https://doi.org/10.1016/0020-0190(89)90137-3
8 https://doi.org/10.1016/0022-0000(81)90012-x
9 https://doi.org/10.1145/78964.78967
10 schema:datePublished 1992
11 schema:datePublishedReg 1992-01-01
12 schema:description In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d+n)log2 n) time, where d is the size of the final display. While the asymptotic performance is the same as that of the previously best known algorithm, our implementation is simpler and more practical, because we try to take full advantage of the specific geometrical properties of the terrain. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O(log2 n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree.
13 schema:editor Nd4d785d0119b4f718bbfac47e944bf16
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N6270a5aa0f7f452c962982b75bdfcbcc
18 schema:name A simplified technique for hidden-line elimination in terrains
19 schema:pagination 133-146
20 schema:productId N589edb58a7e64ad3ac320df35e24693c
21 Ndd579fae2d8e44ee8f3c87ea18568a72
22 Nfe2c31f4da7543ee816680e91d13fd05
23 schema:publisher Nf5766dc7725743d38378eca1ec5a75f8
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049880896
25 https://doi.org/10.1007/3-540-55210-3_179
26 schema:sdDatePublished 2019-04-15T13:04
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N235eb0f9e91249fdb53ff81668de3623
29 schema:url http://link.springer.com/10.1007/3-540-55210-3_179
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N1e268d902cdb4e65aa2adbe4acc4db5e rdf:first N235130d4eab64fc5b524841995a827c6
34 rdf:rest rdf:nil
35 N235130d4eab64fc5b524841995a827c6 schema:familyName Jantzen
36 schema:givenName Matthias
37 rdf:type schema:Person
38 N235eb0f9e91249fdb53ff81668de3623 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N589edb58a7e64ad3ac320df35e24693c schema:name doi
41 schema:value 10.1007/3-540-55210-3_179
42 rdf:type schema:PropertyValue
43 N6270a5aa0f7f452c962982b75bdfcbcc schema:isbn 978-3-540-46775-5
44 978-3-540-55210-9
45 schema:name STACS 92
46 rdf:type schema:Book
47 N7dbd0c94b37c4686abc2c822df0cf532 rdf:first sg:person.0613677314.28
48 rdf:rest rdf:nil
49 Ncc4cb5595c1f4d7886e7e3e2aaa588d8 rdf:first sg:person.012774535455.28
50 rdf:rest N7dbd0c94b37c4686abc2c822df0cf532
51 Nd4d785d0119b4f718bbfac47e944bf16 rdf:first Ne16c14b37aba433792e6ee85bfc40df9
52 rdf:rest N1e268d902cdb4e65aa2adbe4acc4db5e
53 Ndd579fae2d8e44ee8f3c87ea18568a72 schema:name readcube_id
54 schema:value ed9d8ea89d275aa27c9b827a84b790bfd71dd69d2477bffc55b8951f358f35b2
55 rdf:type schema:PropertyValue
56 Ne16c14b37aba433792e6ee85bfc40df9 schema:familyName Finkel
57 schema:givenName Alain
58 rdf:type schema:Person
59 Nf5766dc7725743d38378eca1ec5a75f8 schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 Nfe2c31f4da7543ee816680e91d13fd05 schema:name dimensions_id
63 schema:value pub.1049880896
64 rdf:type schema:PropertyValue
65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
66 schema:name Mathematical Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
69 schema:name Statistics
70 rdf:type schema:DefinedTerm
71 sg:grant.3373848 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-55210-3_179
72 rdf:type schema:MonetaryGrant
73 sg:grant.3382805 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-55210-3_179
74 rdf:type schema:MonetaryGrant
75 sg:person.012774535455.28 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
76 schema:familyName Preparata
77 schema:givenName Franco P.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012774535455.28
79 rdf:type schema:Person
80 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
81 schema:familyName Vitter
82 schema:givenName Jeffrey Scott
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
84 rdf:type schema:Person
85 sg:pub.10.1007/978-1-4612-1098-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021236
86 https://doi.org/10.1007/978-1-4612-1098-6
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf02579170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046501024
89 https://doi.org/10.1007/bf02579170
90 rdf:type schema:CreativeWork
91 https://app.dimensions.ai/details/publication/pub.1021021236 schema:CreativeWork
92 https://doi.org/10.1016/0020-0190(89)90137-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017954086
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0022-0000(81)90012-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048640045
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1145/78964.78967 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047786983
97 rdf:type schema:CreativeWork
98 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
99 schema:name Dept. of Computer Science, Brown University, 02912-1910 Providence, R. I., USA
100 rdf:type schema:Organization
 




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


...