Starburst: a target expansion algorithm for non-uniform target distributions

ABSTRACT

Acquiring small targets on a tablet or touch screen can be challenging. To address the problem, researchers have proposed techniques that enlarge the effective size of targets by extending targets into adjacent screen space. When applied to targets organized in clusters, however, these techniques show little effect because there is no space to grow into. Unfortunately, target clusters are common in many popular applications. We present Starburst, a space partitioning algorithm that works for target clusters. Starburst identifies areas of available screen space, grows a line from each target into the available space, and then expands that line into a clickable surface. We present the basic algorithm and extensions. We then present 2 user studies in which Starburst led to a reduction in error rate by factors of 9 and 3 compared to traditional target expansion.

REFERENCES

• 1: Pär-Anders Albinsson , Shumin Zhai, High precision touch screen interaction, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/642611.642631]
• 2: Patrick Baudisch , Carl Gutwin, Multiblending: displaying overlapping windows simultaneously without the drawbacks of alpha blending, Proceedings of the SIGCHI conference on Human factors in computing systems, p.367-374, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985739]
• 3: Patrick Baudisch , Edward Cutrell , Ken Hinckley , Adam Eversole, Snap-and-go: helping users align objects without the modality of traditional snapping, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1055014]
• 4: Baudisch, P., Cutrell, E., Robbins, D., Czerwinski, M., Tandler, P. Bederson, B., and Zierlinger, A. Drag-and-Pop and Drag-and-Pick: Techniques for Accessing Remote Screen Content on Touch- and Pen-operated Systems. In Proc. Interact'03, pp. 57--64.
• 5: Michel Beaudouin-Lafon , Wendy E. Mackay, Reification, polymorphism and reuse: three principles for designing visual interfaces, Proceedings of the working conference on Advanced visual interfaces, p.102-109, May 2000, Palermo, Italy [doi>10.1145/345513.345267]
• 6: Blaine Bell , Steven Feiner , Tobias Höllerer, View management for virtual and augmented reality, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502363]
• 7: Hrvoje Benko , Andrew D. Wilson , Patrick Baudisch, Precise selection techniques for multi-touch screens, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124963]
• 8: Eric A. Bier , Maureen C. Stone, Snap-dragging, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.233-240, August 1986
• 9: Renaud Blanch , Yves Guiard , Michel Beaudouin-Lafon, Semantic pointing: improving target acquisition with control-display ratio adaptation, Proceedings of the SIGCHI conference on Human factors in computing systems, p.519-526, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985758]
• 10: Dion, J. (1987). Fast printed circuit board routing. ACM Press New York, NY, USA.
• 11: Jean-Daniel Fekete , Catherine Plaisant, Excentric labeling: dynamic neighborhood labeling for data visualization, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.512-519, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303148]
• 12: Fortune, S. A sweepline algorithm for Voronoi diagrams. In Algorithmica 2(1):153--174, March 1987.
• 13: Furnas, G. W. and Qu, Y. Shape manipulation using pixel rewrites. In Proc. Visual Computing 2002 (VC'02), published in Proc. DMS2002, pp. 630--639.
• 14: Tovi Grossman , Ravin Balakrishnan, The bubble cursor: enhancing target acquisition by dynamic resizing of the cursor's activation area, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1055012]
• 15: Tovi Grossman , Ravin Balakrishnan, A probabilistic approach to modeling two-dimensional pointing, ACM Transactions on Computer-Human Interaction (TOCHI), v.12 n.3, p.435-459, September 2005 [doi>10.1145/1096737.1096741]
• 16: Yves Guiard , Renaud Blanch , Michel Beaudouin-Lafon, Object pointing: a complement to bitmap pointing in GUIs, Proceedings of Graphics Interface 2004, p.9-16, May 17-19, 2004, London, Ontario, Canada
• 17: Carl Gutwin, Improving focus targeting in interactive fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems: Changing our world, changing ourselves, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/503376.503424]
• 18: Paul Kabbash , William A. S. Buxton, The “prince” technique: Fitts' law and selection using area cursors, Proceedings of the SIGCHI conference on Human factors in computing systems, p.273-279, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223939]
• 19: Kakoulis, K. and Tollis, I. Intl. Journal of Computational Geometry and Applications 13(1):23--59. (2003).
• 20: Dani Lischinski, Incremental Delaunay triangulation, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 21: Michael J. McGuffin , Ravin Balakrishnan, Fitts' law and expanding targets: Experimental studies and designs for user interfaces, ACM Transactions on Computer-Human Interaction (TOCHI), v.12 n.4, p.388-422, December 2005 [doi>10.1145/1121112.1121115]
• 22: Michael McGuffin , Ravin Balakrishnan, Acquisition of expanding targets, Proceedings of the SIGCHI conference on Human factors in computing systems: Changing our world, changing ourselves, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/503376.503388]
• 23: Parker, J., Mandryk, R., Nunes, M., and Inkpen, K. Improving target acquisition for pointing input on tabletop displays. In Proc. INTERACT 2005, pp 80--93.
• 24: R. L. Potter , L. J. Weldon , B. Shneiderman, Improving the accuracy of touch screens: an experimental evaluation of three strategies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.27-32, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57171]
• 25: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 26: Gonzalo Ramos , Andy Cockburn , Ravin Balakrishnan , Michel Beaudouin-Lafon, Pointing lenses: facilitating stylus input through visual-and motor-space magnification, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240741]
• 27: Andrew Sears , Ben Shneiderman, High precision touchscreens: design strategies and comparisons with a mouse, International Journal of Man-Machine Studies, v.34 n.4, p.593-613, April 1991 [doi>10.1016/0020-7373(91)90037-8]
• 28: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 29: Kishore Swaminathan , Steve Sato, Interaction design for large displays, interactions, v.4 n.1, p.15-24, Jan./Feb. 1997 [doi>10.1145/242388.242395]
• 30: Aileen Worden , Nef Walker , Krishna Bharat , Scott Hudson, Making computers easier for older adults to use: area cursors and sticky icons, Proceedings of the SIGCHI conference on Human factors in computing systems, p.266-271, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258724]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI)

Keywords:
Voronoi, labeling, mouse, pen, target acquisition, target expansion, touch input