Augmenting Holograms

In parallel to the development of computer graphics, and despite their noninteractivity, advances in optical and digital holography have made possible the creation of new fields including interferometry, copy protection, data storage, holographic optical elements, and display holograms. Display holography in particular has conquered several application domains. Optical holograms provide a terapixel resolution and can present information content in the range of terabytes in real time. The goal of the HoloGraphics project at Bauhaus-University Weimar was to investigate possibilities of combining the advantages of conventional holograms with the advantages of today's computer graphics capabilities. This article presents some of the project's findings.     

Augmenting UAV autonomy

The addition of a camera to an unmanned aerial vehicle (UAV) allows the vehicle to perform a variety of tasks autonomously. This paper presents UAV vision systems that were developed and tested at the Georgia Institute of Technology to perform three of these tasks on the GTMax unmanned research helicopter. The first system demonstrates a vision-based navigation system. The second system demonstrates an automated search routine for stationary ground targets. The third system demonstrates a ground target tracking architecture for mobile targets.     

Augmenting photographs with audio

We report a user requirements study of several interfaces for the playback of sounds from photographs. The study showed that users liked listening to audiophotos when the sounds are played back from photographic prints, but as a complement to playback on a PC. When handling prints the audio needs to be invoked manually from the print with a facility to pause the audio during playback. A handheld audioprint player was then designed to fulfill these needs, based on an embedded chip in the paper.     

Augmenting understanding of the relationship between situation awareness and confidence using calibration analysis

The present study represents a preliminary examination of the relationship between situation awareness (SA) and confidence within a distributed information-sharing environment using the calibration methodology. The calibration methodology uses the indices of calibration, resolution and over/under-confidence to examine the relationship between the accuracy of the responses and the degree of confidence that one has in these responses, which leads to a measure of an operator's meta-SA. The results of this study revealed that, although the participants were slightly overconfident in their responses, overall they demonstrated good meta-SA. That is, the participants' subjective probability judgements corresponded to their pattern of SA response accuracy. It is concluded that the use of calibration analysis represents a better methodology for expanding our understanding of the relationship between SA and confidence and ultimately how this relationship can impact decision-making and performance in applied settings than can be achieved by examining SA measures alone.     

Bimagic Vertex Labelings

The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K_{n, n, m}. It is proved that the sequence of bi-regular graphs K_n(ij)?=?((K_n???1???M)?+?K₁)???(u_nu_i)???(u_nu_j) admits 1-vertex bimagic vertex labeling, where u_i, u_j is any pair of non-adjacent vertices in the graph K_n???1???M, u_n is a vertex of K₁, M is perfect matching of the complete graph K_n???1. It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants (n?+?1)(n?+?r)/2?+?n² and (n?+?1)(n?+?r)/2?+?nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined.     

Augmenting Ada for SIMD Parallel Processing

In order to program SIMD (single instruction stream-multiple data stream) parallel machines used for tasks such as speech and image processing, a language with explicit parallel constructs is often desirable. The language Ada, developed by the Department of Defense, is used here as a basis for such a language. Extensions of Ada, which allow the user to specify such operations as interprocessor communications and activation of processors, are proposed. These features are demonstrated by showing their use in a common speech processing algorithm, the parallel FFT.     

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph’s feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters “feedback vertex set number” and “number of vertices to delete”. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the “number of vertices to delete”. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter “feedback edge set number”. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter “vertex cover number and number of vertices to delete”, implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.     

Least Squares Vertex Baking

We investigate the representation of signals defined on triangle meshes using linearly interpolated vertex attributes. Compared to texture mapping, storing data only at vertices yields significantly lower memory overhead and less expensive runtime reconstruction. However, standard approaches to determine vertex values such as point sampling or averaging triangle samples lead to suboptimal approximations. We discuss how an optimal solution can be efficiently calculated using continuous least‐squares. In addition, we propose a regularization term that allows us to minimize gradient discontinuities and mach banding artifacts while staying close to the optimum. Our method has been integrated in a game production lighting tool and we present examples of representing signals such as ambient occlusion and precomputed radiance transfer in real game scenes, where vertex baking was used to free up resources for other game components.     

Vertex Cover Kernelization Revisited

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k ²) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ? coNP/poly and the polynomial hierarchy collapses to the third level.     

Augmenting paper-based learning with mobile phones

Paper and traditional books have been serving as useful tools in supporting knowledge-intensive tasks and school learning. Although learning strategies such as selective verbatim note-taking or question-asking may foster intentional recall or resolve comprehension difficulties in paper-based learning practice, improvement in learning may depend on the opportunity and quality of which students apply note-taking, review notes, or enhance comprehension through questioning. This study aims to complement a paper textbook with a mobile phone and to treat the combination as a whole to facilitate verbatim note-taking, resolving comprehension questions, and receiving reading recommendations. The textbook paragraphs were augmented with line numbers to facilitate coordination between the mobile phone and the paper textbook. An eight-week comparative study was conducted to explore the use of two reading vehicles. The results and findings show that using a mobile phone to augment paper-based learning is technically feasible and seems to promote the application of verbatim note-taking and posting comprehension questions for discussion. However, the results of two course tests indicate that consequent learning improvement seemed inconsistent among the students. A six-week case study was also conducted to explore the implications of the augmented support to students’ learning practice. The findings show that mobile phones as learning supportive tools to augment paper-based learning could support students’ planning and management of learning strategies or activities. The portability of mobile phones and paper textbooks and the ubiquitous connection of paper-based learning with an online learning community may provide the flexibility in planning ahead for suitable learning strategies or activities and may enhance students’ assessment for management of students’ learning goals.     

Augmenting elementary school education with VR

At the University of Illinois at Chicago's Electronic Visualization Laboratory, we use virtual reality technology to complement real-world experiences rather than replace them. For more than two years, we've been deploying ImmersaDesk applications in a Chicago-area elementary school. We want to know whether these virtual environments (VEs) help children make sense of mathematics and scientific phenomena. If so, can educators adapt them to the realities of elementary school learning and teaching? Our experience indicates that VR can successfully augment scientific education as well as help to equalize the learning environment by engaging students of all levels     

Augmenting the aho-corasick pattern matching machine

The Aho-Corasick algorithm is a well-known method of determining the occurrences of one of several given pattern strings in a given text string. We address the question of augmenting the pattern matching machine constructed by this algorithm with a new pattern string, both on-line and off-line. We show that augmenting a machine of N nodes with a new pattern string of length m takes Θ(mN) time on-line and Θ(N) time off-line.     

Proper Interval Vertex Deletion

The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (In: Proceedings WG 2010. Lecture notes in computer science, vol. 6410, pp. 232–243, 2010) showed that this problem can be solved in $\mathcal {O}((14k +14)^{k+1} kn^{6})$ time. We improve this result by presenting an $\mathcal {O}(6^{k} kn^{6})$ time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw,net,tent,C ₄,C ₅,C ₆}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw,net,tent,C ₄,C ₅,C ₆}-free graphs in $\mathcal {O}(n+m)$ time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.     

Augmenting the Connectivity of Outerplanar Graphs

We provide an optimal algorithm for the problem of augmenting an outerplanar graph G by adding a minimum number of edges in such a way that the augmented graph G′ is outerplanar and 2-connected. We also solve optimally the same problem when instead we require G′ to be 2-edge-connected.     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.