Composite Rectilinear Deformation for Stretch and Squish Navigation

James Slack and Tamara Munzner
Transactions on Visualization and Computer Graphics 12(5), September 2006, p 901-908
PDF | Talk | Abstract | Software | Related Papers

Paper: PDF

Abstract

We present the first scalable algorithm that supports the composition of successive rectilinear deformations. Earlier systems that provided stretch and squish navigation could only handle small datasets. More recent work featuring rubber sheet navigation for large datasets has focused on rendering and on application-specific issues. However, no algorithm has yet been presented for carrying out such navigation methods; our paper addresses this problem. For maximum flexibility with large datasets, a stretch and squish navigation algorithm should allow for millions of potentially deformable regions. However, typical usage only changes the extents of a small subset k of these n regions at a time. The challenge is to avoid computations that are linear in n, because a single deformation can affect the absolute screen-space location of every deformable region. We provide an O(k log n) algorithm that supports any application that can lay out a dataset on a generic grid, and show an implementation that allows navigation of trees and gene sequences with millions of items in sub-millisecond time.

Software

Olduvai Sourceforge page

Related Papers

PRISAD - InfoVis 2005 paper
SequenceJuxtaposer - German Conference on Bioinformatics 2004 paper

Talk: Powerpoint


James Slack