9419834
A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes
A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S. Given a set S of n points in ${\Bbb R}^2,$ each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in S move, so the goal is to maintain a triangulation with a small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes $n^2 2^{O(\sqrt{\log n \cdot \log \log n})}$ topological events with high probability if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in $O(\log n)$ time. This is the first known KDS for maintaining a triangulation that processes a near-quadratic number of topological events, and almost matches the $\Omega(n^2)$ lower bound [1]. The number of topological events can be reduced to $nk\cdot 2^{O(\sqrt{\log k \cdot \log\log n})}$ if only k of the points are moving.
15443235
Computing the Writhing Number of a Polygonal Knot
AbstractThe writhing number measures the global geometry of
 a closed space curve or knot.
 We show that this measure is related to the average winding number
 of its Gauss map.
 Using this relationship, we give an algorithm for computing
 the writhing number for a polygonal knot with n edges
 in time roughly proportional to n1.6.
 We also implement a different, simple algorithm and provide
 experimental evidence for its practical efficiency.


312809
Segmenting molecular surfaces
This paper presents a new method for segmentation of molecular surfaces. Topological analysis of a scalar function defined on the surface and its associated gradient field reveals the relationship between the features of interest and critical points of the scalar function. The segmentation is obtained by associating segments with local minima/maxima. Controlled simplification of the function merges segments resulting in a hierarchical segmentation of the molecular surface. This segmentation is used to identify rigid components of protein molecules and to study the role of cavities and protrusions in protein-protein interactions.
378133
LFM-Pro: a tool for detecting significant local structural sites in proteins
MOTIVATION
The rapidly growing protein structure repositories have opened up new opportunities for discovery and analysis of functional and evolutionary relationships among proteins. Detecting conserved structural sites that are unique to a protein family is of great value in identification of functionally important atoms and residues. Currently available methods are computationally expensive and fail to detect biologically significant local features.


RESULTS
We propose Local Feature Mining in Proteins (LFM-Pro) as a framework for automatically discovering family-specific local sites and the features associated with these sites. Our method uses the distance field to backbone atoms to detect geometrically significant structural centers of the protein. A feature vector is generated from the geometrical and biochemical environment around these centers. These features are then scored using a statistical measure, for their ability to distinguish a family of proteins from a background set of unrelated proteins, and successful features are combined into a representative set for the protein family. The utility and success of LFM-Pro are demonstrated on trypsin-like serine proteases family of proteins and on a challenging classification dataset via comparison with DALI. The results verify that our method is successful both in identifying the distinctive sites of a given family of proteins, and in classifying proteins using the extracted features.


AVAILABILITY
The software and the datasets are freely available for academic research use at http://bioinfo.ceng.metu.edu.tr/Pub/LFMPro.
37729130
Extreme Elevation on a 2-Manifold
Given a smoothly embedded 2-manifold in ${\Bbb R}^3,$ we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant under rigid motions and can be used to define features such as lines of discontinuous or continuous but non-smooth elevation. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions and are useful in matching shapes as for example in protein docking.
2273352
Near-Linear Time Approximation Algorithms for Curve Simplification
AbstractWe consider the problem of approximating a polygonal
 curve P under a given error criterion by another
 polygonal curve P’ whose vertices are a
 subset of the vertices of P. The goal is to minimize
 the number of vertices of P’ while ensuring that the
 error between P’ and P is below a certain threshold.
 We consider two different error measures: 
 Hausdorff and Frechet. For both error criteria, we present
 near-linear time approximation algorithms that, given a
 parameter ε > 0, compute a simplified polygonal
 curve P’ whose error is less than ε and
 size at most the size of an optimal simplified
 polygonal curve with error ε/2. We consider
 monotone curves in ℝ2 in the case of the Hausdorff error measure
 under the uniform distance metric
 and arbitrary curves in any dimension for the Frechet error measure
 under Lp metrics. 
 We present
 experimental results demonstrating that our algorithms
 are simple and fast, and produce close to optimal
 simplifications in practice.
5987381
Algorithm performance contest
This contest involved the running and evaluation of computer vision and pattern recognition techniques on different data sets with known groundwidth. The contest included three areas; binary shape recognition, symbol recognition and image flow estimation. A package was made available for each area. Each package contained either real images with manual groundtruth or programs to generate data sets of ideal as well as noisy images with known groundtruth. They also contained programs to evaluate the results of an algorithm according to the given groundtruth. These evaluation criteria included the generation of confusion matrices, computation of the misdetection and false alarm rates and other performance measures suitable for the problems. The paper summarizes the data generation for each area and experimental results for a total of six participating algorithms.
15617422
R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology
Representation of relative spatial relations between objects is often required in many multimedia database applications because spatial relations between objects in an image convey important information about the image. Quantitative representation of spatial relations taking into account shape, size, orientation and distance is often required. The R-Histogram is such a quantitative representation of spatial relations between two objects. However, this method only considers pixels on the object boundary, assuming that the objects are homeomorphic to a 2-ball. For objects with more complicated topology, we propose in this paper the R*-Histogram, a new extension to the R-Histogram. The R*-Histogram generalizes the R-Histogram by taking into account all the pixels in the objects. We also introduce an efficient O(kN log N) time algorithm to compute the R*-Histogram, which is asymptotically faster than the original O(N<sup>2</sup>) time algorithm for the R-Histogram even when k=O(n). Here, N=n<sup>2</sup> denotes the number of pixels in the processed n x n image and k is the number of different directions considered. The effectiveness of the R*-Histogram is evaluated empirically with a Query By Example (QBE) system on a database of 2000 synthetic images containing objects with complicated shape and topology. Experiments have shown that the similarly search results match human intuition very well.
14524485
Boundary finding with correspondence using statistical shape models
We propose an approach for boundary finding where the correspondence of a subset of boundary points to a model is simultaneously determined. Global shape parameters derived from the statistical variation of object boundary points in a training set are used to model the object. A Bayesian formulation, based on this prior knowledge and the edge information of the input image, is employed to find the object boundary with its subset points in correspondence with boundaries in the training set or the mean boundary. We compared the use of a generic smoothness prior and a uniform independent prior with the training set prior in order to demonstrate the power of this statistical information. A number of experiments were performed on both synthetic and real medical images of the brain and heart to evaluate the approach, including the validation of the dependence of the method on image quality, different initialization and prior information.
13312657
Feedback vertex sets in star graphs
In a graph G = (V, E), a subset F ⊂ V(G) is a feedback vertex set of G if the subgraph induced by V(G) \ F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.
13960849
NTS6: IPv6 based Network Topology Service System of CERNET2
In this paper, we propose NTS6, an IPv6 based network topology service system, which provides a query and response service of network topology information between any pair of hosts accessing IPv6 Internet via CERNET2. The NTS6 system periodically collects the latest OSPF, BGP and SNMP information of CERNET2. Based on these information, NTS6 provides network topology information such as net distance, available bandwidth and path packet loss in response to users' query. The real-world experiment on CERNET2 confirms the accuracy of our system. Also, NTS6 now performs well on large deployed maze P2P file-sharing system. We believe NTS6 will be a powerful middleware for other applications.