MOTIVATION: In the past few years, mass spectrometry (MS) has emerged as the premier tool for identification and quantification of biological molecules such as peptides and glycans. There are two basic strategies: single-MS, which uses a single round of mass analysis, and MS/MS (or higher order MS(n)), which adds one or more additional rounds of mass analysis, interspersed with fragmentation steps. Single-MS offers higher throughput, broader mass coverage and more direct quantitation, but generally much weaker identification. Single-MS, however, does work fairly well for the case of N-glycan identification, which are more constrained than other biological polymers. We previously demonstrated single-MS identification of N-glycans to the level of 'cartoons' (monosaccharide composition and topology) by a system that incorporates an expert's detailed knowledge of the biological sample. In this article, we explore the possibility of ab initio single-MS N-glycan identification, with the goal of extending single-MS, or primarily-single-MS, identification to non-expert users, novel conditions and unstudied tissues. RESULTS: We propose and test three cartoon-assignment algorithms that make inferences informed by biological knowledge about glycan synthesis. To test the algorithms, we used 71 single-MS spectra from a variety of tissues and organisms, containing more than 2800 manually annotated peaks. The most successful of the algorithms computes the most richly connected subgraph within a 'cartoon graph'. This algorithm uniquely assigns the correct cartoon to more than half of the peaks in 41 out of the 71 spectra.

Many mobile devices have touch-sensitive screens that people interact with using fingers or thumbs. However, such interaction is difficult because targets become occluded, and because fingers and thumbs have low input resolution. Recent research has addressed occlusion through visual techniques. However, the poor resolution of finger and thumb selection still limits selection speed. In this paper, we address the selection speed problem through a new target selection technique called Escape. In Escape, targets are selected by gestures cued by icon position and appearance. A user study shows that for targets six to twelve pixels wide, Escape performs at a similar error rate and at least 30% faster than Shift, an alternative technique, on a similar task. We evaluate Escape's performance in different circumstances, including different icon sizes, icon overlap, use of color, and gesture direction. We also describe an algorithm that assigns icons to targets, thereby improving Escape's performance.

Clustered sensor networks have been shown to increase system throughput, decrease system delay, and save energy. While those with rotating cluster heads, such as LEACH, have also advantages in terms of security, the dynamic nature of their communication makes most existing security solutions inadequate for them. In this paper, we show how random key predistribution, widely studied in the context of flat networks, can be used to secure communication in hierarchical (cluster-based) protocols such as LEACH. To our knowledge, it is the first work that investigates random key predistribution as applied to hierarchical WSNs

We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.

We describe position sensing algorithms used in an airjet paper moving system built at Xerox PARC. The algorithms combine inputs from optical sensors and compute the rectangle best fitting the data. We consider two different types of sensors: fax scan bars and disk-shaped area sensors. Our algorithms proved to be quite effective both in simulation and in actual use.

We present a new algorithm for automatically solving jigsaw puzzles by shape alone. The algorithm can solve more difficult puzzles than could be solved before, without the use of backtracking or branch-and-bound. The algorithm can handle puzzles in which pieces border more than four neighbors, and puzzles with as many as 200 pieces. Our overall strategy follows that of previous algorithms but applies a number of new ideas, such as robust fiducial points, "highest- confidence-first" search, and frequent global reoptimization of partial solutions.

We describe an algorithm for computing an image signature, suitable for first-stage screening for duplicate images. Our signature relies on the relative brightness of image regions, and is generally applicable to photographs, text documents, and line art. We give experimental results on the sensitivity and robustness of signatures for actual image collections, and also results on the robustness of signatures under transformations such as resizing, rescanning, and compression.

Two images of the same document could differ significantly due to faxing, scanner distortions, or degradation through multigeneration copying. Additionally, one of the images may have extensive annotations not present in the other. We give a method for registering two such images and separating out annotations. We further present an algorithm for detecting and repairing broken strokes in the annotations. Our methods have been tested on a wide variety of documents with reliable results; for the special case of form dropout our results are better than had been obtained previously with special-purpose algorithms.

The regression depth of a hyperplane with respect to a set of n points in R d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d - 1. The k = 0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1 + #)-approximation algorithm for the deepest flat. 1. INTRODUCTION Linear regression asks for an affine subspace (a flat) that fits a set of data points. The most familiar case assumes d-1 independent or explanatory variables and one dependent or response variable, and fits a hyperplane to explain the dependent variable as a linear function of the independent variables. Quite often, however, there may be more than one dependent variable, and the multivariate regression p...

We describe a method for improving scanned or faxed document images. Our method assumes a probabilistic model of the scanning process, and uses this model to cluster instances of the same letter and to compute super-resolved representatives of the clusters. The approach also enables Bayesian prior distributions and reversal of scanner distortions such as gain.

We give a simple combinatorial algorithm that computes a piecewlze-linear approximation of a smooth surface from a finite set of sample points.The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation.We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on "local feature size", the output is topologically valid and convergent (both point&e and in surface normals) to the original surface.We deocribe an implementation of the algorithm and shorr example outputs.

We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3 .The al- gorithm is the first for this problem with provable guarantees.Given a "good sample" from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases.The definition of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples.The output mesh interpolates, rather than approximates, the input points.Our algorithm is based on the three-dimensional Voronoi diagram.Given a good program for this fundamental subroutine, the algorithm is quite easy to implement.

If disks are moved so that each center-center distance does not increase, must the area of their union also be nonincreasing?We show that the answer is yes, assuming that there is a continuous motion such that each center-center distance is a nonincreaaing function of time.This generalizes a previous result on unit disks.Our proof relies on a recent construction of Edelsbrunner and on new isoperimetric inequalities of independent int crest.We go on to show analogous results for the intersection and for holes between disks.

We give some special-case tetrahedralization algorithms. We first consider the problem of finding a tetrahedralization compatible with, a fixed triangulation of the boundary of a polyhedron. We then adapt our solution to the related problem of compat

We give an algorithm for triangulating n-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than π/2. The number of triangles in the triangulation is only O(n), improving a previous bound of O(n2), and the worst-case running time is O(nlog2n). The basic technique used in the algorithm, recursive subdivision by disks, is new and may have wider application in mesh generation. We also report on an implementation of our algorithm.

We give some special-case tetrahedralization algorithms. We first consider the problem of finding a tetrahedralization compatible with a fixed triangulation of the boundary of a polyhedron. We then adapt our solution to the related problem of compatibly tetrahedralizing the interior and exterior of a polyhedron. We also show how to tetrahedralize the region between nested convex polyhedra with O(n log n) tetrahedra and no Steiner points.

We consider graphs such as the minimum spanning tree, minimum Steiner tree, minimum matching, and traveling salesman tour for n points in the d-dimensional unit cube. For each of these graphs, we show that the worst-case sum of the dth powers of edge lengths is O(log n). This is a consequence of a general "gap theorem": for any subadditive geometric graph, either the worst-case sum of edge lengths is O(n (d-1)/d ) and the sum of dth powers is O(log n), or the sum of edge lengths is #(n). We look more closely at some specific graphs: the worst-case sum of dth powers is O(1) for minimum matching, but #(log n) for traveling salesman tour, which answers a question of Snyder and Steele. 1. Introduction A worst-case, or a priori , bound on a geometric graph is a bound that depends only on the assumption that all vertices lie within a given container. Such a bound does not depend on the specific locations of vertices, nor on any probabilistic assumptions. Early papers especially ...

A single physical computer memory may be used for more than one type of page, with the amount of memory devoted to each type under software control.For example, the effective size of memory can be increased by storing some pages in compressed form and decompressing on demand.This introduces another level to the memory hierarchy, and the sizes of two adjacent levels may be varied dynamically.We present an algorithm for varying the mixture of pages in a two-type cache, and then analyze the "competitiveness" of our algorithm.We also report progress in partially automating the design and analysis of on-line algorithms.

We show how to triangulate polygonal regions---adding extra vertices as necessary--- with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. For simple polygons, using O(n log n) triangles, we can guarantee that the largest angle is no greater than 150 ffi . This bound increases to O(n 3=2 ) triangles for the case of polygons with holes. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n 1:85 ) triangles. Keywords: Computational geometry, mesh generation, triangulation, angle condition. 1. Introduction There have been a number of recent papers on the general problem of triangulating a planar point set or pol...

We describe methods for triangulating polygonal re-

Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size.>

Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results.Such checkpoints allow faster recomputation of arbitrary requested points within the computation.We abstract the problem to a server problem in which k servers move along a line in a single direction, modeling the fact that most computations are not reversible.Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server.We present online algorithms and analyze their competitiveness.We give lower bounds on the competitiveness of any online algorithm and show that our algorithms achieve these bounds within relatively small factors.

Abstract We improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem.

Given an undirected n-vertex graph G and a set of n points in Rd, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem are those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

A simple but important special case of the hidden surface removal problem is one in which the scene consists of n rectangles with sides parallel to the x and y-axes, with viewpoint at z = ∞ (that is, an orthographic projection). This special case has application to overlapping windows. An algorithm with running time Ο(n log n log log n + k log n) is given for static scenes, where k is the number of line segments in the output. Algorithms are given for a dynamic setting (that is, rectangles may be inserted and deleted) that take time Ο(log2 n log log n + k log2 n) per insert or delete, where k is now the number of visible line segments that change (appear or disappear). Algorithms for point location in the visible scene are also given.

In recent years, researchers have proven many theorems of the following form: given N points distributed uniformly at random on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these N points is, with probability one, asymptotic to flV~ for some constant fl (which is presumably different for different ~nctionals).Though these theorems are well understood, very little is known about the constants ft.In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ.This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree.We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly with N.

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We present a general methodology for constructing linear time algorithms in the case that the graph G is defined by certain rules of composition (as are trees, series parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a "regular" property (such as independence or matching). This methodology is applied to obtain a linear time algorithm for computing the irredundance number of a tree, a problem for which no polynomial time algorithm was previously known.