We describe a novel technique to provide semi-private feedback on a shared public screen. The technique uses a no-onset presentation that takes advantage of perceptual limitations in human vision to avoid alerting other users to feedback directed at one individual user by suppressing the sudden onset of the feedback. Three experiments evaluated the effectiveness of the technique and appropriate timing parameters and alternatives for presentation onset. Our experiments indicated that an 80 ms no-onset presentation allows participants to interpret information directed to them with over 90% accuracy, but their ability to interpret simultaneously presented information intended for others will be close to random chance. The technique initially camouflages the information being presented by overlaying additional visual elements and then removes those elements to reveal only the elements encoding the information being presented. We discuss applications for the technique, including classroom clicker usage, which was our original motivation for the study.

Design of peer‐review support systems is shaped by the policies that define and govern the process of peer review. An important component of these are policies that deal with anonymity: The rules that govern the concealment and transparency of information related to identities of the various stakeholders (authors, reviewers, editors, and others) involved in the peer‐review process. Anonymity policies have been a subject of debate for several decades within scholarly communities. Because of widespread criticism of traditional peer‐review processes, a variety of new peer‐review processes have emerged that manage the trade‐offs between disclosure and concealment of identities in different ways. Based on an analysis of policies and guidelines for authors and reviewers provided by publication venues, we developed a framework for understanding how disclosure and concealment of identities is managed. We discuss the appropriate role of information technology and computer support for the peer‐review process within that framework.

An important visual cue for the distance to a target is its binocular depth, the disparity between the left and right eyes. We examined mid-air pointing on a large screen, varying the physical distances (depths) to targets. Welford's two-part formulation provided a better model than the one-part Fitts's Law formulation to predict movement time from movement amplitude and target width. Angular measures suggested by Kopper et al. did not improve the model. Consistent variations of Shoemaker et al.'s k-factor suggest target depth plays a role similar to gain for mid-air pointing. We compared both physical and virtual targets to determine if artificial binocular depth cues induce the same performance as purely physical binocular depth cues. Variation of the k-factor was different when virtual depth and physical depth were not identical. This has implications for calibrating 3-D virtual environments and for the design of interactive 3-D pointing techniques for those environments.

A Concept Inventory (CI) is a set of multiple choice questions used to reveal student's misconceptions related to some topic. Each available choice (besides the correct choice) is a distractor that is carefully developed to address a specific misunderstanding, a student wrong thought. In computer science introductory programming courses, the development of CIs is still beginning, with many topics requiring further study and analysis. We identify, through analysis of open-ended exams and instructor interviews, introductory programming course misconceptions related to function parameter use and scope, variables, recursion, iteration, structures, pointers and boolean expressions. We categorize these misconceptions and define high-quality distractors founded in words used by students in their responses to exam questions. We discuss the difficulty of assessing introductory programming misconceptions independent of the syntax of a language and we present a detailed discussion of two pilot CIs related to parameters: an open-ended question (to help identify new misunderstandings) and a multiple choice question with suggested distractors that we identified.

UD Co-Spaces (Urban Design Collaborative Spaces) is an integrated, tabletop-centered multi-display environment for engaging the public in the complex process of collaborative urban design. We describe the iterative user-centered process that we followed over six years through a close interdisciplinary collaboration involving experts in urban design and neighbourhood planning. Versions of UD Co-Spaces were deployed in five real-world charrettes (planning workshops) with 83 participants, a heuristic evaluation with three domain experts, and a qualitative laboratory study with 37 participants. We reflect on our design decisions and how multi-display environments can engage a broad range of stakeholders in decision making and foster collaboration and co-creation within urban design. We examine the parallel use of different displays, each with tailored interactive visualizations, and whether this affects what people can learn about the consequences of their choices for sustainable neighborhoods. We assess UD Co-Spaces using seven principles for collaborative urban design tools that we identified based on literature in urban design, CSCW, and public engagement.

Recruiting qualified reviewers, though challenging, is crucial for ensuring a fair and robust scholarly peer review process. We conducted a survey of 307 reviewers of submissions to the International Conference on Human Factors in Computing Systems (CHI 2011) to gain a better understanding of their motivations for reviewing. We found that encouraging high‐quality research, giving back to the research community, and finding out about new research were the top general motivations for reviewing. We further found that relevance of the submission to a reviewer's research and relevance to the reviewer's expertise were the strongest motivations for accepting a request to review, closely followed by a number of social factors. Gender and reviewing experience significantly affected some reviewing motivations, such as the desire for learning and preparing for higher reviewing roles. We discuss implications of our findings for the design of future peer review processes and systems to support them.

Scholarly peer review is a complex collaborative activity that is increasingly supported by web‐based systems, yet little is known about how reviewers and authors interact in such environments, how criticisms are conveyed, or how the systems may affect the interactions and use of language of reviewers and authors. We looked at one aspect of the interactions between reviewers and authors, the use of politeness in reviewers' comments. Drawing on B rown and L evinson's (1987) politeness theory, we analyzed how politeness strategies were employed by reviewers to mitigate their criticisms in an open peer‐review process of a special track of a human‐computer interaction conference. We found evidence of frequent use of politeness strategies and that open peer‐review processes hold unique challenges and opportunities for using politeness strategies. Our findings revealed that less experienced researchers tended to express unmitigated criticism more often than did experienced researchers, and that reviewers tended to use more positive politeness strategies (e.g., compliments) toward less experienced authors. Based on our findings, we discuss implications for research communities and the design of peer‐reviewing processes and the information systems that support them.

We report a study of how dual display screens were used in classroom lectures for university-level courses across a variety of disciplines during five academic terms over a 2-year period. Our goal was to understand the pedagogical consequences of using more than a single electronic display screen to support classroom lectures. We deployed an in-house software system (MultiPresenter) in real classrooms. We examined the use of MultiPresenter by 8 university instructors who taught 15 courses with a total of 1,147 students during 13-week regular terms or 6-week summer terms. We observed classroom lectures, interviewed instructors, collected screen images and log files of MultiPresenter usage, and administered questionnaires to students about their subjective impressions. Based on these data, we analyzed how instructors used MultiPresenter in order to identify examples of how multiple display screens might best be used for educational purposes. The analysis revealed that the following practices are beneficial: the ability to keep information persistent for extended periods, the increased flexibility in where and when information is shown, capability for side-by-side comparison of full screens of information, simultaneous visibility of both overview (“roadmap”) and detailed (“content”) information, and extra space to annotate information. Possible hazards include difficulty focusing on specific information amidst a large amount of information and too much information changing too quickly without proper indication of the changes.

We establish that two-part models of pointing performance (Welford’s model) describe pointing on a computer display significantly better than traditional one-part models (Fitts’s Law). We explore the space of pointing models and describe how independent contributions of movement amplitude and target width to pointing time can be captured in a parameter k . Through a reanalysis of data from related work we demonstrate that one-part formulations are fragile in describing pointing performance, and that this fragility is present for various devices and techniques. We show that this same data can be significantly better described using two-part models. Finally, we demonstrate through further analysis of previous work and new experimental data that k increases linearly with gain. Our primary contribution is the demonstration that Fitts’s Law is more limited in applicability than previously appreciated, and that more robust models, such as Welford’s formulation, should be adopted in many cases of practical interest.

Recent keyboard-based alternatives to WIMP interfaces do not have good support for commands that require multiple parameters. We remedy this by extending a previous design and mimicking dialog boxes to provide good visual feedback while still keeping the advantages of keyboard input. A laboratory study showed the new technique to be competitive with dialog boxes on speed and error rate, but strongly preferred over dialog boxes by experienced command line users. This is a marked improvement over the previous design, which was also preferred by the target user group but did not compete with dialog boxes in terms of performance.

Large classrooms have traditionally provided multiple blackboards on which an entire lecture could be visible. In recent decades, classrooms were augmented with a data projector and screen, allowing computer-generated slides to replace hand-written blackboard presentations and overhead transparencies as the medium of choice. Many lecture halls and conference rooms will soon be equipped with multiple projectors that provide large, high-resolution displays of comparable size to an old fashioned array of blackboards. The predominant presentation software, however, is still designed for a single medium-resolution projector. With the ultimate goal of designing rich presentation tools that take full advantage of increased screen resolution and real estate, we conducted an observational study to examine current practice with both traditional whiteboards and blackboards, and computer-generated slides. We identify several categories of observed usage, and highlight differences between traditional media and computer slides. We then present design guidelines for presentation software that capture the advantages of the old and the new and describe a working prototype based on those guidelines that more fully utilizes the capabilities of multiple displays.

We introduce MultiPresenter, a novel presentation system designed to work on very large display spaces (multiple displays or physically large high-resolution displays). MultiPresenter allows presenters to organize and present pre-made and dynamic presentations that take advantage of a very large display space accessed from a personal laptop. Presenters can use the extra space to provide long-term persistency of information to the audience. Our design deliberately separates content generation (authoring) from the presentation of content. We focus on supporting presentation flow and a variety of presentation styles, ranging from automated, scripted sequences of pre-made slides to highly dynamic ad-hoc, and non-linear content. By providing smooth transition between these styles, presenters can easily alter the flow of content during a presentation to adapt to an audience or to change emphasis in response to emerging interests. We describe our goals, rationale and the design process, providing a detailed description of the current version of the system, and discuss our experience using it throughout a one-semester first year computer science course.

Physical controls such as knobs, sliders, and buttons are experiencing a revival as many computing systems progress from personal computing architectures towards ubiquitous computing architectures. We demonstrate a process for measuring and comparing visceral emotional responses of a physical control to performance results of a target acquisition task. In our user study, participants experienced mechanical and rendered friction, inertia, and detent dynamics as they turned a haptic knob towards graphical targets of two different widths and amplitudes. Together, this process and user study provide novel affect- and performance-based design guidance to developers of physical controls for emerging ubiquitous computing environments. Our work bridges extensive human factors work in mechanical systems that peaked in the 1960's, to contemporary trends, with a goal of integrating mechatronic controls into emerging ubiquitous computing systems.

We introduce Shadow Reaching, an interaction technique that makes use of a perspective projection applied to a shadow representation of a user. The technique was designed to facilitate manipulation over large distances and enhance understanding in collaborative settings. We describe three prototype implementations that illustrate the technique, examining the advantages of using shadows as an interaction metaphor to support single users and groups of collaborating users. Using these prototypes as a design probe, we discuss how the three components of the technique (sensing, modeling, and rendering) can be accomplished with real (physical) or computed (virtual) shadows, and the benefits and drawbacks of each approach.

Two approaches for supporting personalization in complex software are system-controlled adaptive menus and user-controlled adaptable menus. We evaluate a novel interface design for feature-rich productivity software based on adaptable menus. The design allows the user to easily customize a personalized interface, and also supports quick access to the default interface with all of the standard features. This design was prototyped as a front-end to a commercial word processor. A field experiment investigated users' personalizing behavior and tested the effects of different interface designs on users' satisfaction and their perceived ability to navigate, control, and learn the software. There were two conditions: a commercial word processor with adaptive menus and our prototype with adaptable menus for the same word processor. Our evaluation shows: (1) when provided with a flexible, easy-to-use and easy-to-understand customization mechanism, the majority of users do effectively personalize their interface; and (2) user-controlled interface adaptation with our adaptable menus results in better navigation and learnability, and allows for the adoption of different personalization strategies, as compared to a particular system-controlled adaptive menu system that implements a single strategy. We report qualitative data obtained from interviews and questionnaires with participants in the evaluation in addition to quantitative data.

Most co-authoring tools support basic annotations, such as edits and comments that are anchored at specific locations in the document. However, they do not support meta-commentary about a document (such as an author's summary of modifications) which gets separated from the document, often in the body of email messages. This causes unnecessary overhead in the write-review-edit workflow inherent in co-authoring. We present document-embedded structured annotations called "bundles" that incorporate the meta-commentary into a unified annotation model that meets a set of annotation requirements we identified through a small field investigation. A usability study with 20 subjects evaluated the annotation reviewing stage of co-authoring and showed that annotation bundles in our high-fidelity prototype reduced reviewing time and increased accuracy, compared to a system that only supports edits and comments.

Most graphical user interfaces provide visual cursors to facilitate interaction with input devices such as mice, pointers, and pens. These cursors often include directional cues that could influence the stimulus-response compatibility of user input. We conducted a controlled evaluation of four cursor orientations and an orientation-neutral cursor in a circular menu selection task. Mouse interaction on a desktop, pointer (i.e. wand) interaction on a large screen, and pen interaction on a Tablet PC were evaluated. Our results suggest that choosing appropriate cursors is especially important for pointer interaction, but may be less important for mice or pens. Cursors oriented toward the lower-right corner of a display yielded the poorest performance overall while orientation-neutral cursors were generally the best. Advantages were found for orientations aligned with the direction of movement. We discuss these results and suggest guidelines for the appropriate use of cursors in various input and display configurations.

Collaboration often relies on all group members having a shared view of a single-user application. A common situation is a single active presenter sharing a live view of her workstation screen with a passive audience, using simple hardware-based video signal projection onto a large screen or simple bitmap-based sharing protocols. This offers simplicity and some advantages over more sophisticated software-based replication solutions, but everyone has the exact same view of the application. This conflicts with the presenter's need to keep some information and interaction details private. It also fails to recognize the needs of the passive audience, who may struggle to follow the presentation because of verbosity, display clutter or insufficient familiarity with the application.Views that cater to the different roles of the presenter and the audience can be provided by custom solutions, but these tend to be bound to a particular application. In this paper we describe a general technique and implementation details of a prototype system that allows standardized role-specific views of existing single-user applications and permits additional customization that is application-specific with no change to the application source code. Role-based policies control manipulation and display of shared windows and image buffers produced by the application, providing semi-automated privacy protection and relaxed verbosity to meet both presenter and audience needs.

Sociological and technical difficulties, such as a lack of informal encounters, can make it difficult for new members of noncollocated software development teams to learn from their more experienced colleagues. To address this situation, we have developed a tool, named Hipikat that provides developers with efficient and effective access to the group memory for a software development project that is implicitly formed by all of the artifacts produced during the development. This project memory is built automatically with little or no change to existing work practices. After describing the Hipikat tool, we present two studies investigating Hipikat's usefulness in software modification tasks. One study evaluated the usefulness of Hipikat's recommendations on a sample of 20 modification tasks performed on the Eclipse Java IDE during the development of release 2.1 of the Eclipse software. We describe the study, present quantitative measures of Hipikat's performance, and describe in detail three cases that illustrate a range of issues that we have identified in the results. In the other study, we evaluated whether software developers who are new to a project can benefit from the artifacts that Hipikat recommends from the project memory. We describe the study, present qualitative observations, and suggest implications of using project memory as a learning aid for project newcomers.

Computer-aided design (CAD) and 3D visualization techniques are at the heart of many engineering processes such as aircraft, ship, and automobile design. These visualization tasks require users to navigate or wayfind through complex 3D geometric models consisting of millions of parts. Despite numerous studies, it remains unclear whether large-screen displays improve user performance for such activities. We present a user study comparing standard desktop, immersive room (i.e., CAVE), and wall displays with 3D stereo/head-tracking, and mono/no head-tracking. We observed individual differences between users and found that the presence of contextual structure greatly impacted performance, suggesting that providing structure and developing interaction techniques accommodating a wide range of users yields better performance than focusing on display characteristics alone.

Enabling group collaboration is important in computer graphics today. We have developed a framework that supports multiple pointing devices to explore the collaborative utility of multiple mice and laser pointer interaction in graphical environments. Because most pointing device comparisons are done in the context of single user performance, very little is known about the affordances of collaborating with multiple pointing devices. We present an experimental comparison of mouse pointer to laser pointer interaction in a problem-solving task involving groups of one, two, and three people. We show that collaborative performance is largely orthogonal to motor performance and that the interaction patterns are dependent on the task and on the group size. This suggests that the collaborative characteristics of a pointing device are just as important as the physical characteristics that are usually given the most attention, such as precision and accuracy.

Neuroanatomical evidence indicates the human eye's visual field can be functionally divided into two vertical hemifields, each specialized for specific functions. The upper visual field (UVF) is specialized to support perceptual tasks in the distance, while the lower visual field (LVF) is specialized to support visually-guided motor tasks, such as pointing. We present a user study comparing mouse- and touchscreen-based pointing for items presented in the UVF and LVF on an interactive display. Consistent with the neuroscience literature, we found that mouse and touchscreen pointing were faster and more accurate for items presented in the LVF when compared to pointing at identical targets presented in the UVF. Further analysis found previously unreported performance differences between the visual fields for touchscreen pointing that were not observed for mouse pointing. This indicates that a placement of interactive items favorable to the LVF yields superior user performance, especially for systems dependent on direct touch interactions.

The lack of lightweight communication channels and other technical and sociological difficulties make it hard for new members of a non-collocated software development team to learn effectively from their more experienced colleagues while they are coming up-to-speed on a project. To address this situation, we have developed a tool, named Hipikat, that provides developers with efficient and effective access to the group memory for a software development project that is implicitly formed by all of the artifacts produced during the development. This project memory is built automatically with little or no change to existing work practices. We report an exploratory case study evaluating whether software developers who are new to a project can benefit from the artifacts that Hipikat recommends from the project memory. To assess the appropriateness of the recommendations, we investigated when and how developers queried the project memory, how the evaluated the recommended artifacts, and the process by which they utilized the artifacts. We found that newcomers did use the recommendations and their final solutions exploited the recommended artifacts, although most of the Hipikat queries came in the early stages of a change task. We describe the case study, present qualitative observations, and suggest implications of using project memory as a learning aid for project newcomers.

This study examines a novel interface design for heavily-featured productivity software. The design includes two interfaces between which the user can easily toggle: (1) an interface personalized by the user containing desired features only, and (2) the default interface with all the standard features. This design was prototyped as a front-end to a commercial word processor and evaluated in a comprehensive field study. The study tested the effects of different interface designs on users' satisfaction and their perceived ability to navigate, control, and learn the software. There were two conditions: a commercial word processor with adaptive menus and our two-interface prototype with adaptable menus for the same word processor. Results showed that participants were better able to navigate through the menus and toolbars and were better able to learn with our prototype. There were also significant differences in satisfaction and control with our design

Many computer operating systems provide seamless support for multiple display screens, but there are few cross-platform tools for collaborative use of multiple computers in a shared display environment. Mighty Mouse is a novel groupware tool built on the public domain VNC protocol. It is tailored specifically for face-to-face collaboration where multiple heterogeneous computers (usually laptops) are viewed simultaneously (usually via projectors) by people working together on a variety of applications under various operating systems. Mighty Mouse uses only the remote input capability of VNC, but enhances this with various features to support flexible movement between the various platforms, "floor control" to facilitate smooth collaboration, and customization features to accommodate different user, platform, and application preferences in a relatively seamless manner. The design rationale arises from specific observations about how people collaborate in meetings, which allows certain simplifying assumptions to be made in the implementation.

This paper describes a project to explore issues surrouding the development of a collaborative handheld educational application for children. A user-centered, iterative design process was used to develop GeneyTM, a collaborative problem solving application to help children explore genetic concepts using PalmTM handheld computers. The design methodology utilized mock-ups of representative tasks and scenarios, pre-design meetings with targets users, prototype development, and feedback sessions with target users. The results of this work identify an effective way of utilizing handheld computers for collaborative learning and provide important insights into the design of handheld applications for children. This work also illustrates the necessity of user-centered design when new user groups are targeted, especially when novel user interface paradigms are employed that go beyond current windows-based interfaces.

We describe a simple technique for accurately calibrating the temporal lag in augmented and virtual environments within the Enhanced Virtual Hand Lab (EVHL), a collection of hardware and software to support research on goal-directed human hand motion. Lag is the sum of various delays in the data pipeline associated with sensing, processing, and displaying information from the physical world to produce an augmented or virtual world. Our main calibration technique uses a modified phonograph turntable to provide easily tracked periodic motion, reminiscent of the pendulum-based calibration technique of Liang, Shaw and Green. Measurements show a three-frame (50 ms) lag for the EVHL. A second technique, which uses a specialized analog sensor that is part of the EVHL, provides a "closed loop" calibration capable of sub-frame accuracy. Knowing the lag to sub-frame accuracy enables a predictive tracking scheme to compensate for the end-toend lag in the data pipeline. We describe both techniques and the EVHL environment in which they are used.

The Virtual Hand Lab (VHL) is an an augmented reality envimnment for conducting experiments in human perception and motor performance that involve grasping, manipulation, and other 3D tasks that people perform with their hands.The hardware and software testbed supports both physical and virtual objects, and object behaviors that cm be specified in advance by experimenters.A testbed for conducting experiments must provide visual stimuli that depend on the configuration of the experimental apparatus, on the specific tasks that are being studied, and on the individual characteristics of each subject.Calibration is an important concern and is the subject of this paper.A proper design leads to independent calibration steps that modularize the subsystems that require calibration and explicitly recognize and order the dependencies among them.We describe how the architecture for the VHL was designed to support independent apparatus-specific, experiment-specific, and subject-specific calibrations.The architecture offers benefits for any augmented reality environment by reducing m-calibration times and identifying appropriate modularization in the software that can result in a more robust and efficient implementation.

An experiment was conducted to investigate the relationship between object transportation and object orientation by the human hand in the context of humancomputer interaction (HCI). This work merges two streams of research: the structure of interactive manipulation in HCI and the natural hand prehension in human motor control. It was found that object transportation and object orientation have a parallel, interdependent structure which is generally persistent over different visual feedback conditions. The notion of concurrency and interdependence of multidimensional visuomotor control structure can provide a new framework for human-computer interface evaluation and design. Keywords Direct manipulation, input device, multi-dimensional control, visuomotor control, visual conditions, information processing, interface design, virtual reality. INTRODUCTION Object manipulation is a basic operation in humancomputer interaction (HCI). Modern computer technology advances towards affording m...

The present study investigated the ability to interactively locate points in a three dimensional computer environment using a six degree of freedom input device. Four different visual feedback modes were tested: fixed viewpoint monoscopic perspective, fixed viewpoint stereoscopic perspective, head-tracked monoscopic perspective and head-tracked stereoscopic perspective. Targets were located at plus and minus 10cm along the X, Y or Z axes, from a fixed starting location. Data about the time to complete the task and positioning accuracy (error) are gathered for each trial. In addition, subjective feedback regarding the apparatus, visual mode and task difficulty was solicited from subjects. The results indicate that stereoscopic performance is superior to monoscopic performance and that asymmetries exist both across and within axes. Head tracking had no appreciable effect upon performance. Subjective feedback regarding performance is usually consistent with objective measures, but some in...

A new method is presented for performing rapid and accurate numerical estimation. The method is derived from an area of human cognitive psychology called preattentive processing. Preattentive processing refers to an initial organization of the visual field based on cognitive operations believed to be rapid, automatic, and spatially parallel. Examples of visual features that can be detected in this way include hue, intensity, orientation, size, and motion. We beleive that studies from preattentive vision should be used to assist in the design of visualization tools, especially those for which high-speed target detection, boundary identification, and region detection are important. In our present study, we investigated two known preattentive features (hue and orientation) in the context of a new task (numerical estimation) in order to see whether preattentive estimation was possible. Our experiments tested displays that were designed to visualize data from salmon migration simulations. The results showed that rapid and accurate estimation was indeed possible using either hue or orientation. Furthermore, random variation in one of these features resulted in no interference when subjects estimated the percentage of the other. To test the generality of our results, we varied two important display parameters—display duration and feature difference—and found boundary conditions for each. Implications of our results for application to real-world data and tasks are discussed.

There are a variety of spline formulations for specifying smooth curves.In theory, many of these are equivalent in terms of the families of curves that can be obtained.In practice, each formulation encourages the implementation of certain styles of interaction in a curve editor and discourages other styles.This paper presents the design, implementation, and analysis of four experiments to illustrate a general shape-matching paradigm for studying interactive curve manipulation.We introduce the new shape-matching paradigm as a methodology for analyzing user performance.We then report on a series of studies that employ this paradigm to explore the relationship between a commonly used interaction style for curve design and various spline formulations, Controlled experiments were performed to test the hypothesis that the style of interaction implicit in the movement of single design points will influence the ease with which curve manipulation can be performed using a variety of spline formulations.Although such interactions are of a simple form, the experience gained in these studies has already enabled us to undertake more extensive experiments with more sophisticated interaction styles.The specific experiments reported here compare five formulations of cubic splines (B-splines, B6zier splines, Catmull-Rom splines, and two versions of interpolating splines with C 2 continuity), Data from the experiments show that, for the particular shape-matching tasks investigated, there is a significant performance difference among the five formulations.The B-spline formulation was best for the task, both in terms of match quality and in terms of the time required to Financial support for this research was provided by the

Fish tank virtualreality" refers to the use of a standard graphics workstation to achieve real-time display of 3D scenes using stereopsis and dynamic head-coupled perspective.Fish tank VR has a number of advantages over head-mounted immersion VR which makes it more practical for many applications.After discussing the characteristics of fish tank VR, we describe a set of three experiments conducted to study the benefits of fish tank VR over a traditional workstation graphics display.These experiments tested user performance under two conditions: (a) whether or not stereoscopic display was used and (b) whether or not the perspective display was coupled dynamically to the positions of a user's eyes.Subjects using a comparison protocol consistently preferred head coupling without stereo over stereo without head coupling.Error rates in a tree-tracing task similar to one used by Sollenberger and Milgram showed an order of magnitude improvement for head-coupled stereo over a static (nonhead-coupled) display, and the benefits gained by head coupling were more significant than those gained from stereo alone.The final experiment examined two factors that are often associated with human performance in virtual worlds: the lag (or latency) in receiving and processing tracker data arid the rate at which frames are updated.For the tree-tracing task, lag had a larger impact on performance than did frame update rate, with lag having a multiplicative effect on response time.We discuss the relevance of these results for the display of complex 3D data and highlight areas requiring further study, Categories and Subject Descriptors: 1.

A two-part experiment was conducted to investigate the effects of aliasing artifacts and screen resolution on a simple visual recognition task. The results indicate that in many cases far less realism may be necessary in synthetic computer-generated imagery than is often assumed in the literature. The first part of the experiment comprised a subjective rating of image quality, the second part measured task effectiveness of image quality. In the second part subjects were asked to discriminate between images of two types of objects built from cubes, similar to objects used in experiments involving mental rotation.

An innovative design for an interactive paint program has been developed based on multiple processes and message passing. Traditional paint programs combine interrupt-driven support of a graphical input device, such as a mouse or tablet, with the coloring of pixels in a raster display. We advocate a different design methodology which is illustrated in our implementation. The multiple processes and message passing primitives provided by some real-time operating systems encourage the design of parallel-program architectures and anthropomorphic programming structures, analogous to artist procedures and the metaphors of Smalltalk.

A set of vertices D is a dominating set for a graph if every vertex is either in D or adjacent to a vertex which is in D. We show that the problem of finding a minimum dominating set in a chordal graph is NP-complete, even when restricted to undirected path graphs, but exhibit a linear time greedy algorithm for the problem further restricted to directed path graphs. Streamlined to handle only trees, our algorithm becomes the algorithm of Cockayne, Goodman and Hedetniemi. An interesting parallel with graph isomorphism is pointed out.

An algorithm based upon Edmonds’s procedure for testing isomorphism of trees is extended to answer various questions concerning automorphisms of a labeled forest. This and linear pattern matching techniques are used to build efficient algorithms which find the automorphism partition and a set of generators for the automorphism group, determine the order of the automorphism group, and compute a coding for forests, interval graphs, outerplanar graphs, and planar graphs.

A graph is an interval graph tf and only if each of Its verttces can be associated with an interval on the real hne m such a way that two vertices are adjacent m the graph exactly when the corresponding mtervals have a nonempty mtersectmn An effictent algonthrn for testing tsomorpinsm of interval graphs ts unplemented using a data structure called a PQ-tree.The algorithm runs m O(n + e) steps for graphs having n vemces and e edges It is shown that for a somewhat larger class of graphs, namely the chordal graphs, lsomorpinsm is as hard as for general graphs KEY WORDS AND PHRASES graph tsomorpinsm algonthms, polynomial reduclinhty, intersection graphs, interval graphs, chordal graphs, ngtd clrcmt graphs CR CATEGORIES. 5 25, 5.32 Permission to copy without fee all or part of tins material ,s granted provtded that the

Two problems are polynomially equivalent if each is polynomially reducible to the other. The problems of testing either two graphs, two semigroups, or two finite automata for isomorphism are shown to be polynomially equivalent. For graphs the isomorphism problem may be restricted to regular graphs since we show that this is equivalent to the general case. Using the techniques of Hartmanis and Berman we then show that this equivalence is actually a polynomial isomorphism. It is conjectured that the isomorphism problem for groups is not in this equivalence class, but that it is an easier problem. If the conjecture is true then $P \ne NP$; if it is false then there exists a “subexponential” $O(n^{c_1 \log n + c_2 } )$ algorithm for graph isomorphism.

A matrix of zeroes and ones is said to have the consecutive ones property if there is a permutation of its rows such that the ones in each column appear consecutively. This paper develops a data structure which may be used to test a matrix for the consecutive ones property, and produce the desired permutation of the rows, in linear time. One application of the consecutive ones property is in recognizing interval graphs. A graph is an interval graph if there exists a 1-1 correspondence between its vertices and a set of intervals on the real line such that two vertices are adjacent if and only if the corresponding intervals have a nonempty intersection. Fulkerson and Gross have characterized interval graphs as those for which the clique versus vertex incidence matrix has the consecutive ones property. In testing this particular matrix for the consecutive ones property we may process the columns in a special order to simplify the algorithm. This yields the interval graph recognition algorithm which is presented in section 2; section 3 indicates how this algorithm may be extended to the general consecutive ones problem.

Chess is a warlike game descended from a long line of games with military overtones.However, many chess players feel that the element of complete information in chess is incompatible with a realistic model of war.Kriegspiel introduces an explicit element of incomplete information into chess without the use of a chance device.This is accomplished by screening each player's men from the opponent's view.Because the legality of a move in chess depends on the positions of all 32 men, neither player in a game of Kriegspiel can determine if a given move is legal.Thus a third participant is necessary.This third participant, the direct or §, enforces the rules of Kriegspiel, keeps a record of the game, and controls communications between the players.(In addition, the director controls the kibitzers, who are an important part of the Kriegspiel atmosphere.)These tasks are normally accomplished with a chess board, pencil and paper, and a commanding voice.This paper describes a pair of computer programs which act as director for Kriegspiel.The programs are implemented on a time-shared graphics-oriented computer.In this environment, a large portion of the director's task is communication, either between the players or between the director and one player.This aspect of the director is not intimately connected with Kriegspiel-the problems and solutions we discuss apply to many gaming situations.We have separated communications from the strictly rules-enforcing portion of the programs; communications are handled by the Kriegspiel monitor, which calls a referee subprogram when there are rules decisions to be made.The referee never communicates directly with the players.Kriegspiel has been the subject of at least one previous paper, Burger (1967), which describes a considerably more primitive director.The rules for Kriegspiel are not standardised, but there is a large measure of agreement on them.Both Harkness (1967) and Gollon (1968) give rules.A surge of Kriegspiel activity occurred within the scientific community after a memorandum by Williams (1950).We were encouraged to publish by an article of Bell (1970) which describes a referee for chess.Our referee in the Kriegspiel director is more powerful than that of Bell and may be used to control either chess or Kriegspiel.The details of the referee are described in a separate paper (Buckholtz and Wetherell, 1970).