^April May – 2010 ^June

In this paper we present a new approach for interactive view-dependent rendering of large polygonal datasets, which relies on advanced features of modern graphics hardware. Our preprocessing algorithm starts by generating a simplified representation of the input mesh. It then builds a multiresolution hierarchy for the simplified model. For each face in the hierarchy, it generates and assigns a displacement map that resembles the original surface represented by that face. At runtime, the multiresolution hierarchy is used to select a coarse viewdependent level-of-detail representation, which is sent to the graphics hardware. The GPU then refines the coarse representation by replacing each face with a planar patch, which is elevated according to the assigned displacement map. Initial results show that our implementation achieves quality images at high rates.

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The {em energy} of a transmission path from node $u$ to node $v$ is the sum of the squares of the distances between adjacent nodes along the path. For a constant $t >1$, an energy $t$-spanner is a graph $G'$, such that for any two nodes $u$ and $v$, there exists a path from $u$ to $v$ in $G'$, whose energy is at most $t$ times the energy of a minimum-energy path from $u$ to $v$ in the complete Euclidean graph.

We study the problem of finding a power assignment, such that (i) its induced communication graph is a `good' energy spanner, and (ii) its cost is `low'. We show that for any constant $t >1$, one can find a power assignment, such that its induced communication graph is an energy $t$-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph).

Based on joint work with Rom Aschner, Paz Carmi and Matya Catz.