Constructing Binary Space Partitions for Orthogonal Rectangles in Practice View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-03-15

AUTHORS

T. M. Murali , Pankaj K. Agarwal , Jeffrey Scott Vitter

ABSTRACT

In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in ℝ3. Our algorithm has the novel feature that it tunes its performance to the geometric properties of the rectangles, e.g., their aspect ratios. We have implemented our algorithm and tested its performance on real data sets. We have also systematically compared the performance of our algorithm with that of other techniques presented in the literature. Our studies show that our algorithm constructs BSPs of near-linear size and small height in practice, has fast running times, and answers queries efficiently. It is a method of choice for constructing BSPs for orthogonal rectangles. More... »

PAGES

211-222

References to SciGraph publications

Book

TITLE

Algorithms — ESA’ 98

ISBN

978-3-540-64848-2
978-3-540-68530-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-68530-8_18

DOI

http://dx.doi.org/10.1007/3-540-68530-8_18

DIMENSIONS

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


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/2005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Literary Studies", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing Department of Computer Science, Duke University, Box 90129, 27708-0129, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Murali", 
        "givenName": "T. M.", 
        "id": "sg:person.012336662245.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012336662245.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing Department of Computer Science, Duke University, Box 90129, 27708-0129, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Agarwal", 
        "givenName": "Pankaj K.", 
        "id": "sg:person.01346666674.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01346666674.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing Department of Computer Science, Duke University, Box 90129, 27708-0129, Durham, NC"
          ], 
          "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": "sg:pub.10.1007/bf02187806", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006487892", 
          "https://doi.org/10.1007/bf02187806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187806", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006487892", 
          "https://doi.org/10.1007/bf02187806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-60313-1_148", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012313329", 
          "https://doi.org/10.1007/3-540-60313-1_148"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/97880.97892", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016785205"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(92)90007-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045895260"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/74334.74343", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048002892"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/253284.253326", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052078905"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/37402.37421", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063169296"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/965105.807481", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063175364"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4613-8713-8_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1089511031", 
          "https://doi.org/10.1007/978-1-4613-8713-8_8"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-03-15", 
    "datePublishedReg": "2002-03-15", 
    "description": "In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in \u211d3. Our algorithm has the novel feature that it tunes its performance to the geometric properties of the rectangles, e.g., their aspect ratios. We have implemented our algorithm and tested its performance on real data sets. We have also systematically compared the performance of our algorithm with that of other techniques presented in the literature. Our studies show that our algorithm constructs BSPs of near-linear size and small height in practice, has fast running times, and answers queries efficiently. It is a method of choice for constructing BSPs for orthogonal rectangles.", 
    "editor": [
      {
        "familyName": "Bilardi", 
        "givenName": "Gianfranco", 
        "type": "Person"
      }, 
      {
        "familyName": "Italiano", 
        "givenName": "Giuseppe F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Pietracaprina", 
        "givenName": "Andrea", 
        "type": "Person"
      }, 
      {
        "familyName": "Pucci", 
        "givenName": "Geppino", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-68530-8_18", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64848-2", 
        "978-3-540-68530-2"
      ], 
      "name": "Algorithms \u2014 ESA\u2019 98", 
      "type": "Book"
    }, 
    "name": "Constructing Binary Space Partitions for Orthogonal Rectangles in Practice", 
    "pagination": "211-222", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-68530-8_18"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "68e932c1f7f05d6294b2270f71cf7da543c7724582916708921c7c81b5a83322"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022020356"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-68530-8_18", 
      "https://app.dimensions.ai/details/publication/pub.1022020356"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:35", 
    "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/0000000346_0000000346/records_99832_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-68530-8_18"
  }
]
 

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-68530-8_18'

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-68530-8_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-68530-8_18'

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-68530-8_18'


 

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

124 TRIPLES      23 PREDICATES      35 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-68530-8_18 schema:about anzsrc-for:20
2 anzsrc-for:2005
3 schema:author N4e91d745826a4abb83cb879afe12103b
4 schema:citation sg:pub.10.1007/3-540-60313-1_148
5 sg:pub.10.1007/978-1-4613-8713-8_8
6 sg:pub.10.1007/bf02187806
7 https://doi.org/10.1016/0196-6774(92)90007-y
8 https://doi.org/10.1145/253284.253326
9 https://doi.org/10.1145/37402.37421
10 https://doi.org/10.1145/74334.74343
11 https://doi.org/10.1145/965105.807481
12 https://doi.org/10.1145/97880.97892
13 schema:datePublished 2002-03-15
14 schema:datePublishedReg 2002-03-15
15 schema:description In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in ℝ3. Our algorithm has the novel feature that it tunes its performance to the geometric properties of the rectangles, e.g., their aspect ratios. We have implemented our algorithm and tested its performance on real data sets. We have also systematically compared the performance of our algorithm with that of other techniques presented in the literature. Our studies show that our algorithm constructs BSPs of near-linear size and small height in practice, has fast running times, and answers queries efficiently. It is a method of choice for constructing BSPs for orthogonal rectangles.
16 schema:editor N48abac0ae2d04fbe9b0083dd3e6f7316
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N2e697cac3d014ca9869d0fe43ba4daf0
21 schema:name Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
22 schema:pagination 211-222
23 schema:productId N2314e0c9fa07450690c36b2c1f8cdaac
24 N32d4f4bc30b74a7e974d481d36a2c20f
25 N935e713cf1ad4be7821903c4cc364b10
26 schema:publisher Nd905e6a4e6264a0dad8df93cb966de60
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022020356
28 https://doi.org/10.1007/3-540-68530-8_18
29 schema:sdDatePublished 2019-04-16T05:35
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N2b653708a94342d8afdef0924e0c94fb
32 schema:url https://link.springer.com/10.1007%2F3-540-68530-8_18
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N2314e0c9fa07450690c36b2c1f8cdaac schema:name readcube_id
37 schema:value 68e932c1f7f05d6294b2270f71cf7da543c7724582916708921c7c81b5a83322
38 rdf:type schema:PropertyValue
39 N2b653708a94342d8afdef0924e0c94fb schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N2e697cac3d014ca9869d0fe43ba4daf0 schema:isbn 978-3-540-64848-2
42 978-3-540-68530-2
43 schema:name Algorithms — ESA’ 98
44 rdf:type schema:Book
45 N2fab2553fb4446cf8158acd8126b6cbf rdf:first N422719e70b7a4fc2992d7af70f1fead2
46 rdf:rest Nfaffc6d51f63496eadf231dfbf2b7508
47 N32d4f4bc30b74a7e974d481d36a2c20f schema:name doi
48 schema:value 10.1007/3-540-68530-8_18
49 rdf:type schema:PropertyValue
50 N422719e70b7a4fc2992d7af70f1fead2 schema:familyName Italiano
51 schema:givenName Giuseppe F.
52 rdf:type schema:Person
53 N48abac0ae2d04fbe9b0083dd3e6f7316 rdf:first Ne6f6a0e782dc4929b93d70777b418930
54 rdf:rest N2fab2553fb4446cf8158acd8126b6cbf
55 N4e91d745826a4abb83cb879afe12103b rdf:first sg:person.012336662245.14
56 rdf:rest N8da47dd6bebb468ba28ddfbb3ed7d6b7
57 N5e1af55e3d684aca829b927f00227cbf schema:familyName Pucci
58 schema:givenName Geppino
59 rdf:type schema:Person
60 N8da47dd6bebb468ba28ddfbb3ed7d6b7 rdf:first sg:person.01346666674.21
61 rdf:rest Ncef3b2aab6f44146b04e57af72c71d38
62 N935e713cf1ad4be7821903c4cc364b10 schema:name dimensions_id
63 schema:value pub.1022020356
64 rdf:type schema:PropertyValue
65 Nab9fb18719e24ae98b360c3e6d6ba16b rdf:first N5e1af55e3d684aca829b927f00227cbf
66 rdf:rest rdf:nil
67 Ncef3b2aab6f44146b04e57af72c71d38 rdf:first sg:person.0613677314.28
68 rdf:rest rdf:nil
69 Nd905e6a4e6264a0dad8df93cb966de60 schema:location Berlin, Heidelberg
70 schema:name Springer Berlin Heidelberg
71 rdf:type schema:Organisation
72 Ne5c7e61ccb6b41788d5eb71852b3a99c schema:familyName Pietracaprina
73 schema:givenName Andrea
74 rdf:type schema:Person
75 Ne6f6a0e782dc4929b93d70777b418930 schema:familyName Bilardi
76 schema:givenName Gianfranco
77 rdf:type schema:Person
78 Nfaffc6d51f63496eadf231dfbf2b7508 rdf:first Ne5c7e61ccb6b41788d5eb71852b3a99c
79 rdf:rest Nab9fb18719e24ae98b360c3e6d6ba16b
80 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
81 schema:name Language, Communication and Culture
82 rdf:type schema:DefinedTerm
83 anzsrc-for:2005 schema:inDefinedTermSet anzsrc-for:
84 schema:name Literary Studies
85 rdf:type schema:DefinedTerm
86 sg:person.012336662245.14 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
87 schema:familyName Murali
88 schema:givenName T. M.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012336662245.14
90 rdf:type schema:Person
91 sg:person.01346666674.21 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
92 schema:familyName Agarwal
93 schema:givenName Pankaj K.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01346666674.21
95 rdf:type schema:Person
96 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
97 schema:familyName Vitter
98 schema:givenName Jeffrey Scott
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
100 rdf:type schema:Person
101 sg:pub.10.1007/3-540-60313-1_148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012313329
102 https://doi.org/10.1007/3-540-60313-1_148
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/978-1-4613-8713-8_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089511031
105 https://doi.org/10.1007/978-1-4613-8713-8_8
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/bf02187806 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006487892
108 https://doi.org/10.1007/bf02187806
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0196-6774(92)90007-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1045895260
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/253284.253326 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052078905
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1145/37402.37421 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063169296
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1145/74334.74343 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048002892
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1145/965105.807481 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063175364
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/97880.97892 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016785205
121 rdf:type schema:CreativeWork
122 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
123 schema:name Center for Geometric Computing Department of Computer Science, Duke University, Box 90129, 27708-0129, Durham, NC
124 rdf:type schema:Organization
 




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


...