Geometric algorithms for message filtering in decentralized virtual environments

Yohai Makbily, Craig Gotsman, Reuven Bar-Yehuda

Research output: Contribution to conferencePaperpeer-review

21 Scopus citations


Distributed virtual environments impose a heavy load on the network upon which they reside. Bandwidth is a potential bottleneck because n users imply O(n2) update messages per time unit, which is prohibitive for a large number of users. Efficient message filtering is called for, in both centralized systems, having a central server, and decentralized systems, having no central server. We solve the message filtering problem for decentralized multi-user systems based on geometric virtual worlds, popular in interactive 3D graphics applications. This is achieved by exploiting the visual relevance relationship (based on proximity, visibility and direction criteria) between pairs of users to compute mutually irrelevant regions in user parameter space. These regions are then used as up-date-free regions (UFR's); i.e. no communication between users is required while they are in their respective regions. Geometric algorithms for computing UFR's for the proximity, visibility and direction relevance criteria are described. Our implementation and experimental results show that the message-filtering algorithm is output-sensitive. Use of our algorithms is especially effective where messages are sent through a slow communication network, such as the Internet.

Original languageEnglish (US)
Number of pages8
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 Symposium on Interactive 3D Graphics - Atlanta, GA, USA
Duration: Apr 26 1999Apr 28 1999


ConferenceProceedings of the 1999 Symposium on Interactive 3D Graphics
CityAtlanta, GA, USA

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Geometric algorithms for message filtering in decentralized virtual environments'. Together they form a unique fingerprint.

Cite this