Automatically assigned DDC number: 006696

Manually assigned DDC number: 006693

Number of references: 8

Title: Binary Space Partitions for Fat Rectangles

Author:

Author:

Author:

Author:

Subject: Pankaj K. Agarwal,Edward F. Grove,T. M. Murali,Jeffrey Scott Vitter Binary Space Partitions for Fat Rectangles

Description: We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in R 3 such that the aspect ratio of each rectangle in S is at most ff, for some constant ff 1. We present an n2 O( p log n ) -time algorithm to build a binary space partition of size n2 O( p log n ) for S. We also show that if m of the n rectangles in S have aspect ratios greater than ff, we can construct a BSP of size n p m2 O( p log n ) for S in n p m2 O( p log n ) time. The constants of proportionality in the big-oh terms are linear in log ff. We extend these results to cases in which the input contains non-orthogonal or intersecting objects. Support was provided by National Science Foundation research grant CCR--93--01259, by Army Research Office MURI grant DAAH04--96--1--0013, by a Sloan fellowship, by a National Science Foundation NYI award and matching funds from Xerox Corp, and by a grant from the U...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-05-05

Pubyear: 1997

Format: ps

Identifier: http://citeseer.ist.psu.edu/148425.html

Source: ftp://ftp.cs.duke.edu/dist/techreport/1997/1997-09.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/74155.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Computational   Geometry"   CiteSeer_Volume=""   Title="Cylindrical   Static   and   Kinetic   Binary   Space   Partitions,">

            <identifier   Org="ISBN:0521848628"   Paper_ID="/74155.html"   Extracted="0521848628"   DDC="516/.11"   Normalized_DDC="51611"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0819457213"   Paper_ID="/74155.html"   Extracted="0819457213"   />

            <identifier   Org="ISBN:0898714109"   Paper_ID="/74155.html"   Extracted="0898714109"   />

            <identifier   Org="ISBN:0898716055"   Paper_ID="/74155.html"   Extracted="0898716055"   />

            <identifier   Org="ISBN:1568810814"   Paper_ID="/74155.html"   Extracted="1568810814"   DDC="629.8/92"   Normalized_DDC="629892"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1568812353"   Paper_ID="/74155.html"   Extracted="1568812353"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1584883014"   Paper_ID="/74155.html"   Extracted="1584883014"   DDC="516/.13"   Normalized_DDC="51613"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1584884355"   Paper_ID="/74155.html"   Extracted="1584884355"   DDC="005.7/3"   Normalized_DDC="00573"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1591405408"   Paper_ID="/74155.html"   Extracted="1591405408"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:160566054X"   Paper_ID="/74155.html"   Extracted="160566054X"   DDC="004.165"   Normalized_DDC="004165"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540435948"   Paper_ID="/74155.html"   Extracted="3540435948"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540662278"   Paper_ID="/74155.html"   Extracted="3540662278"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:9812569081"   Paper_ID="/74155.html"   Extracted="9812569081"   DDC="006.42"   Normalized_DDC="00642"   Normalized_Weight="0.1"   />

      </rec>

      <rec   ID="/342425.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Modeling   Global   Diffuse   Illumination   for   Image   Synthesis,">

            <identifier   Org="ISBN:0121782700"   Paper_ID="/342425.html"   Extracted="0121782700"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="1.0"   />

            <identifier   Org="ISBN:0769521711"   Paper_ID="/342425.html"   Extracted="0769521711"   />

            <identifier   Org="ISBN:078033762X"   Paper_ID="/342425.html"   Extracted="078033762X"   />

            <identifier   Org="ISBN:8483013282"   Paper_ID="/342425.html"   Extracted="8483013282"   />

      </rec>

      <rec   ID="/144935.html"   Type="inproceedings"   CiteSeer_Book="Graphics   Interface   95"   CiteSeer_Volume=""   Title="Near-Optimal   Construction   of   Partitioning   Trees   by   Evolutionary   Techniques,">

            <identifier   Org="ISBN:0898714109"   Paper_ID="/144935.html"   Extracted="0898714109"   />

      </rec>

      <rec   ID="/158871.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="The   Object   Complexity   Model   of   Hidden-Surface   Rendering,"   />

      <rec   ID="/401391.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Computational   Geometry"   CiteSeer_Volume=""   Title="Approximation   Algorithms   for   Geometric   Tour   and   Network   Design   Problems   (Extended   Abstract),">

            <identifier   Org="ISBN:3540275800"   Paper_ID="/401391.html"   Extracted="3540275800"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540715894"   Paper_ID="/401391.html"   Extracted="3540715894"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540728686"   Paper_ID="/401391.html"   Extracted="3540728686"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.3333333333333333"   />

      </rec>

      <rec   ID="/132026.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Interactive   3D   Graphics"   CiteSeer_Volume=""   Title="Consistent   Solid   and   Boundary   Representations   from   Arbitrary   Polygonal   Data,">

            <identifier   Org="ISBN:0471139467"   Paper_ID="/132026.html"   Extracted="0471139467"   DDC="621.3/03"   Normalized_DDC="621303"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:0769521711"   Paper_ID="/132026.html"   Extracted="0769521711"   />

            <identifier   Org="ISBN:0818682620"   Paper_ID="/132026.html"   Extracted="0818682620"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:0897918843"   Paper_ID="/132026.html"   Extracted="0897918843"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:0898714109"   Paper_ID="/132026.html"   Extracted="0898714109"   />

            <identifier   Org="ISBN:1581130805"   Paper_ID="/132026.html"   Extracted="1581130805"   />

            <identifier   Org="ISBN:1581133669"   Paper_ID="/132026.html"   Extracted="1581133669"   />

            <identifier   Org="ISBN:1581135068"   Paper_ID="/132026.html"   Extracted="1581135068"   />

      </rec>

      <rec   ID="/505639.html"   Type="inproceedings"   CiteSeer_Book="CGI93"   CiteSeer_Volume=""   Title="Constructing   Good   Partitioning   Trees,">

            <identifier   Org="ISBN:0201624206"   Paper_ID="/505639.html"   Extracted="0201624206"   />

            <identifier   Org="ISBN:0818628979"   Paper_ID="/505639.html"   Extracted="0818628979"   />

            <identifier   Org="ISBN:089791953X"   Paper_ID="/505639.html"   Extracted="089791953X"   DDC="006"   Normalized_DDC="006"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:1558607323"   Paper_ID="/505639.html"   Extracted="1558607323"   DDC="794.8/1526"   Normalized_DDC="79481526"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:155860801X"   Paper_ID="/505639.html"   Extracted="155860801X"   DDC="006.6/96"   Normalized_DDC="006696"   Normalized_Weight="0.3333333333333333"   />

      </rec>

      <rec   ID="/504015.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   Graphics   Interface   92"   CiteSeer_Volume=""   Title="Interactive   solid   geometry   via   partitioning   trees,">

            <identifier   Org="ISBN:0769506437"   Paper_ID="/504015.html"   Extracted="0769506437"   DDC="006.6/96"   Normalized_DDC="006696"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0780329880"   Paper_ID="/504015.html"   Extracted="0780329880"   />

            <identifier   Org="ISBN:0897916727"   Paper_ID="/504015.html"   Extracted="0897916727"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0897918843"   Paper_ID="/504015.html"   Extracted="0897918843"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0898714109"   Paper_ID="/504015.html"   Extracted="0898714109"   />

            <identifier   Org="ISBN:155860801X"   Paper_ID="/504015.html"   Extracted="155860801X"   DDC="006.6/96"   Normalized_DDC="006696"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:1568810814"   Paper_ID="/504015.html"   Extracted="1568810814"   DDC="629.8/92"   Normalized_DDC="629892"   Normalized_Weight="0.2"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Binary   Space   Partitions   for   Fat   Rectangles">

            <identifier   Org="ISBN:0521848628"   Paper_ID="SELF"   Extracted="0521848628"   DDC="516/.11"   Normalized_DDC="51611"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:078033762X"   Paper_ID="SELF"   Extracted="078033762X"   />

            <identifier   Org="ISBN:078039979X"   Paper_ID="SELF"   Extracted="078039979X"   />

            <identifier   Org="ISBN:0821842390"   Paper_ID="SELF"   Extracted="0821842390"   DDC="516/.13"   Normalized_DDC="51613"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:1584883014"   Paper_ID="SELF"   Extracted="1584883014"   DDC="516/.13"   Normalized_DDC="51613"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540200649"   Paper_ID="SELF"   Extracted="3540200649"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540240586"   Paper_ID="SELF"   Extracted="3540240586"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540405453"   Paper_ID="SELF"   Extracted="3540405453"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

      </rec>

</references_metadata>