Self-customized BSP trees for collision detection

Sigal Ar, Bernard Chazelle, Ayellet Tal

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


The ability to perform efficient collision detection is essential in virtual reality environments and their applications, such as walkthroughs. In this paper we re-explore a classical structure used for collision detection -the binary space partitioning tree. Unlike the common approach, which attributes equal likelihood to each possible query, we assume events that happened in the past are more likely to happen again in the future. This leads us to the definition of self-customized data structures. We report encouraging results obtained while experimenting with this concept in the context of self-customized BSP trees.

Original languageEnglish (US)
Pages (from-to)91-102
Number of pages12
JournalComputational Geometry: Theory and Applications
Issue number1-3
StatePublished - Feb 2000

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Binary space partitioning
  • Collision detection
  • Self-customization


Dive into the research topics of 'Self-customized BSP trees for collision detection'. Together they form a unique fingerprint.

Cite this