Writhe

The writhing number is a standard measure of the global geometry of a closed space curve. We give an algorithm for computing the writhing number for a polygonal knot with n edges in time O(n^{1.6+}), for any arbitrarily small constant >0. We implement a simple algorithm, which works in O(n log n) time in practice, and provide experimental evidence for its practical efficiency.

 

Scalable Simulator for Forest Dynamics
This software is developed as part of an interdisciplinary project between Computer Science and Ecology. We have developed an individual based, spatially explicit forest growth model. We have implemented a simulator that simulates the evoution of such a forest. We have designed efficient algorithms using techniques that include:
• Using graphics hardware for fast geometric computation • Hierarchical spatial decomposition using quad-tree like structures • Monopole approximation
These techniques allow us to efficiently simulate large forests (few sq. kilometres) for long periods of time (few thousand time steps).
Graphics-Hardware Based Algorithms
Geometric Optimization : Graphics hardware based algorithms for efficiently computing several shape measures such as width, diameter, bounding box and penetration depth
Depth Contour: Graphics hardware based algorithm for several data-depth problems
Map Simplification: Graphics hardware based algorithm for map simplification

Core Sets
This software includes practical implementations for computing the core set of points in any dimension, and various shape fitting problems and kinetic data structures using core sets.


Curve Simplification
Near-linear algorithms for curve simplification in two and three dimensions. Software for approximating a piece-wise linear curve with fewer vertices. Implements the factor-2 approximation algorithm.

CRB-tree: an I/O Efficient Data Structure for Orthogonal Range Counting
We have devoped an I/O efficient data structure for performing range aggregate query. The data structure has been implemented in the TPIE framework at Duke. Currently our implementation can perform range counting queries in 2D.

 

 

k-Means Projective Clustering
A k-means type algorithm for projective clustering