Article

Free access

Kinetic binary space partitions for intersecting segments and disjoint triangles

Authors:

Pankaj K. Agarwal,

Jeff Erickson,

Leonidas J. GuibasAuthors Info & Claims

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

Pages 107 - 116

Published: 01 January 1998 Publication History

PDF eReader

References

[1]

P. K. Agarwal, L. J. Guibas, T. M. Murali, and J. S. Vitter. Cylindrical static and kinetic binary space partitions. Proc. 13th Annu. ACM Sympos. Comput. Geom., pp. 39-48, 1997.

Digital Library

Google Scholar

[2]

J. M. Airey. Increasing Update Rates in the Building Walkthrough System with Automatic Model-space Subdivision and Potentially Visible Set Calculations. Ph.D. thesis, Dept. of Computer Science, University of North Carolina, Chapel Hill, 1990.

Digital Library

Google Scholar

[3]

M. J. Atallah. Some dynamic computational geometry problems. Comput. Math. Appl. 11:1171-1181, 1985.

Google Scholar

[4]

C. Ballieux. Motion planning using binary space partitions. Tech. Rep. Inf/src/93-25, Utrecht University, 1993.

Google Scholar

[5]

J. Basch, L. Guibas, and J. Hershberger. Data structures for mobile data. Proc. 8th A CM-SIAM Sympos. Discrete Algorithms, pp. 747-756, 1997.

Digital Library

Google Scholar

[6]

T. Cassen, K. R. Subramanian, and Z. Michalewicz. Near-optimal construction of partitioning trees by evolutionary techniques. Proc. Graphics Interface '95, pp. 263-271, 1995.

Google Scholar

[7]

N. Chin and S. Feiner. Near real-time shadow generation using BSP trees. Comput. Graph. 23:99-106, 1989. Proc. SIGGRAPH '89.

Digital Library

Google Scholar

[8]

N. Chin and S. Feiner. Fast object-precision shadow generation for areal light sources using BSP trees. Cornput. Graph. 25:21-30., Mar. 1992. Proc. 1992 Sympos. Interactive 3D Graphics.

Digital Library

Google Scholar

[9]

Y. Chrysanthou. Shadow Computation .for 319 Interaction and Animation. Ph.D. thesis, Queen Mary and Westfield College, University of London, 1996.

Google Scholar

[10]

J.D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, and Phillips. introduction to Computer Graphics. Addison- Wesley, Reading, MA, 1993.

Digital Library

Google Scholar

[11]

H. FUchs, Z. M. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. Comput. Graph. 14:124-133, 1980. Proc. SIGGRAPH '80.

Digital Library

Google Scholar

[12]

S. Kahan. A model for data in motion. Proc. $3th Annu. A CM Sympos. Theory Comput., pp. 267-277, 1991.

Digital Library

Google Scholar

[13]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, 1995.

Digital Library

Google Scholar

[14]

T. M. Murali and T. A. Funkhouser. Consistent solid and boundary representations from arbitrary polygonal data. Proc. 1997 Sympos. Interactive 31) Graphics, 1997.

Digital Library

Google Scholar

[15]

B. Naylor, J. A. Amanatides, and W. Thibault. Merging BSP trees yields polyhedral set operations. Comput. Graph. 24:115-124, Aug. 1990. Proc. SIGGRAPH '90.

Digital Library

Google Scholar

[16]

B. Naylor and W. Thibault. Application of BSP trees to ray-tracing and CSG evaluation. Technical Report GIT-ICS 86/03, Georgia Institute of Tech., School of Information and Computer Science, Feb. 1986.

Google Scholar

[17]

B.F. Naylor. Interactive solid geometry via partitioning trees. Proc. Graphics Interface '92, pp. 11-18, 1992.

Digital Library

Google Scholar

[18]

T. Ottmann and D. Wood. Dynamical sets of points. Comput. Vision Graph. Image Process. 27:157-166, 1984.

Google Scholar

[19]

M. S. Paterson and F. F. Yao. Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom. 5:485-503, 1990.

Google Scholar

[20]

M. S. Paterson and F. F. Yao. Optimal binary space partitions for orthogonal objects. J. Algorithms 13:99- 113, 1992.

Digital Library

Google Scholar

[21]

R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp. Study for applying computer-generated images to visual simulation. Tech. Rep. AFHRL-TR-69- 14, U.S. Air Force Human Resources Laboratory, 1969.

Google Scholar

[22]

M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

Digital Library

Google Scholar

[23]

S. J. Teller. Visibility Computations in Densely Occluded Polyhedral Environments. Ph.D. thesis, Dept. of Computer Science, University of California, Berkeley, 1992.

Digital Library

Google Scholar

[24]

W. C. Thibault and B. F. Naylor. Set operations on polyhedra using binary space partitioning trees. Cornput. Graph. 21:153-162, 1987. Proc. SIGGRAPH '87.

Digital Library

Google Scholar

[25]

E. Torres. Optimization of the binary space partition algorithm (BSP) for the visualization of dynamic scenes. Eurographics '90, pp. 507-518, 1990.

Google Scholar

Cited By

View all

Liu YCrabbe MLi RDong RManta OComite U(2020)A Study on Spatial Layout of Tourist Attractions Based on POIProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436309(118-123)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436309
lixi YCrabbe MLi RDong RManta OComite U(2020)A Space-time Analysis of Tourism Information Flow Based on SNA InformationProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436308(109-117)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436308
Renping ZCrabbe MLi RDong RManta OComite U(2020)A Study on the Spatiotemporal Distribution of POI TouristsProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436307(103-108)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436307
Show More Cited By

Index Terms

Kinetic binary space partitions for intersecting segments and disjoint triangles

Recommendations

Binary space partitions for axis-paralles line segments: size-height tradeoffs

We present worst-case lower bounds on the minimum size of a binary space partition (BSP) tree as a function of its height, for a set S of n axis-parallel line segments in the plane. We assume that the BSP uses only axis-parallel cutting lines. These ...
Binary plane partitions for disjoint line segments
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition, where each step partitions the space (and some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open ...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
SCG '01: Proceedings of the seventeenth annual symposium on Computational geometry

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

January 1998

704 pages

ISBN:0898714109

Chairman:
Howard Karloff

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Check for updates

Qualifiers

Article

Conference

SODA98

Sponsor:

SIGACT
SIAM

SODA98: 1998 Conference on Discrete Algorithms

January 25 - 27, 1998

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
403
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)9

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu YCrabbe MLi RDong RManta OComite U(2020)A Study on Spatial Layout of Tourist Attractions Based on POIProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436309(118-123)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436309
lixi YCrabbe MLi RDong RManta OComite U(2020)A Space-time Analysis of Tourism Information Flow Based on SNA InformationProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436308(109-117)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436308
Renping ZCrabbe MLi RDong RManta OComite U(2020)A Study on the Spatiotemporal Distribution of POI TouristsProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436307(103-108)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436307
Jiang SFan YGuo SLi Bchen Y(2019)An Analysis of Employment Satisfaction of Business English Majors under the background of Belt and Road InitiativeProceedings of the 2019 3rd International Workshop on Education, Big Data and Information Technology10.1145/3352740.3352749(48-53)Online publication date: 28-Jun-2019
https://dl.acm.org/doi/10.1145/3352740.3352749
Ying LRenping ZAli R(2019)Research on the Influence of National System along "the Belt and Road Initiative" on Investment Area Selection Based on Mult-Motivation Analysis of Intelligent Modeling and Information ProcessingProceedings of the 2019 International Conference on Data Mining and Machine Learning10.1145/3335656.3335689(75-80)Online publication date: 28-Apr-2019
https://dl.acm.org/doi/10.1145/3335656.3335689
Renping ZYing LAli R(2019)Research on offline behavior similarity of consumers based on Spatio-temporal data set miningProceedings of the 2019 International Conference on Data Mining and Machine Learning10.1145/3335656.3335684(49-53)Online publication date: 28-Apr-2019
https://dl.acm.org/doi/10.1145/3335656.3335684
Yan-Ying FZi-Min ZGuan-Ping CShi-Yong Z(2019)The extraction research on evaluation rules for students based on discernibility matrixProceedings of the 2019 International Conference on Data Mining and Machine Learning10.1145/3335656.3335680(28-33)Online publication date: 28-Apr-2019
https://dl.acm.org/doi/10.1145/3335656.3335680
Evans WKirkpatrick DLöffler MStaals Fda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Competitive query strategies for minimising the ply of the potential locations of moving pointsProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462395(155-164)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462395
Degener BGehweiler JLammersen C(2010)Kinetic Facility LocationAlgorithmica10.5555/3118227.311848157:3(562-584)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.5555/3118227.3118481
Agarwal PKaplan HSharir M(2008)Kinetic and dynamic data structures for closest pair and all nearest neighborsACM Transactions on Algorithms10.1145/1435375.14353795:1(1-37)Online publication date: 12-Dec-2008
https://dl.acm.org/doi/10.1145/1435375.1435379
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Binary space partitions for axis-paralles line segments: size-height tradeoffs

Binary plane partitions for disjoint line segments

Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles