Archives for 2006

Today I read a paper titled “Single-Strip Triangulation of Manifolds with Arbitrary Topology”

The abstract is:
Triangle strips have been widely used for efficient rendering.

It is NP-complete to test whether a given triangulated model can be represented as a single triangle strip, so many heuristics have been proposed to partition models into few long strips.

In this paper, we present a new algorithm for creating a single triangle loop or strip from a triangulated model.

Our method applies a dual graph matching algorithm to partition the mesh into cycles, and then merges pairs of cycles by splitting adjacent triangles when necessary.

New vertices are introduced at midpoints of edges and the new triangles thus formed are coplanar with their parent triangles, hence the visual fidelity of the geometry is not changed.

We prove that the increase in the number of triangles due to this splitting is 50% in the worst case, however for all models we tested the increase was less than 2%.

We also prove tight bounds on the number of triangles needed for a single-strip representation of a model with holes on its boundary.

Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves on a manifold of any arbitrary topology.

Today I read a paper titled “A New Approach to Draw Detection by Move Repetition in Computer Chess Programming”

The abstract is:
We will try to tackle both the theoretical and practical aspects of a very important problem in chess programming as stated in the title of this article – the issue of draw detection by move repetition.

The standard approach that has so far been employed in most chess programs is based on utilising positional matrices in original and compressed format as well as on the implementation of the so-called bitboard format.

The new approach that we will be trying to introduce is based on using variant strings generated by the search algorithm (searcher) during the tree expansion in decision making.

We hope to prove that this approach is more efficient than the standard treatment of the issue, especially in positions with few pieces (endgames).

To illustrate what we have in mind a machine language routine that implements our theoretical assumptions is attached.

The routine is part of the Axon chess program, developed by the authors.

Axon, in its current incarnation, plays chess at master strength (ca.

2400-2450 Elo, based on both Axon vs computer programs and Axon vs human masters in over 3000 games altogether).

Today I read a paper titled “Nearly optimal exploration-exploitation decision thresholds”

The abstract is:
While in general trading off exploration and exploitation in reinforcement learning is hard, under some formulations relatively simple solutions exist.

Optimal decision thresholds for the multi-armed bandit problem, one for the infinite horizon discounted reward case and one for the finite horizon undiscounted reward case are derived, which make the link between the reward horizon, uncertainty and the need for exploration explicit.

From this result follow two practical approximate algorithms, which are illustrated experimentally.

Today I read a paper titled “How to Simulate Billiards and Similar Systems”

The abstract is:
An N-component continuous-time dynamic system is considered whose components evolve autonomously all the time except for in discrete asynchronous instances of pairwise interactions.

Examples include chaotically colliding billiard balls and combat models.

A new efficient serial event-driven algorithm is described for simulating such systems.

Rather than maintaining and updating the global state of the system, the algorithm tries to examine only essential events, i.e., component interactions.

The events are processed in a non-decreasing order of time; new interactions are scheduled on the basis of the examined interactions using preintegrated equations of the evolutions of the components.

If the components are distributed uniformly enough in the evolution space, so that this space can be subdivided into small sectors such that only O(1) sectors and O(1)$components are in the neighborhood of a sector, then the algorithm spends time O (log N) for processing an event which is the asymptotical minimum.

The algorithm uses a simple strategy for handling data: only two states are maintained for each simulated component.

Fast data access in this strategy assures the practical efficiency of the algorithm.

It works noticeably faster than other algorithms proposed for this model.

Key phrases: collision detection, dense packing, molecular dynamics, hard spheres, granular flow .

Today I read a paper titled “The `Face on Mars’: a photographic approach for the search of signs of past civilizations from a macroscopic point of view, factoring long-term erosion in image reconstruction”

The abstract is:
This short article presents an alternative view of high resolution imaging from various sources with the aim of the discovery of potential sites of archaeological importance, or sites that exhibit `anomalies’ such that they may merit closer inspection and analysis.

It is conjectured, and to a certain extent demonstrated here, that it is possible for advanced civilizations to factor in erosion by natural processes into a large scale design so that main features be preserved even with the passage of millions of years.

Alternatively viewed, even without such intent embedded in a design left for posterity, it is possible that a gigantic construction may naturally decay in such a way that even cataclysmic (massive) events may leave sufficient information intact with the passage of time, provided one changes the point of view from high resolution images to enhanced blurred renderings of the sites in question.

Today I read a paper titled “Clustering Techniques for Marbles Classification”

The abstract is:
Automatic marbles classification based on their visual appearance is an important industrial issue.

However, there is no definitive solution to the problem mainly due to the presence of randomly distributed high number of different colours and its subjective evaluation by the human expert.

In this paper we present a study of segmentation techniques, we evaluate they overall performance using a training set and standard quality measures and finally we apply different clustering techniques to automatically classify the marbles.

KEYWORDS: Segmentation, Clustering, Quadtrees, Learning Vector Quantization (LVQ), Simulated Annealing (SA).

Today I read a paper titled “Quantum Algorithm Processor For Finding Exact Divisors”

The abstract is:
Wiring diagrams are given for a quantum algorithm processor in CMOS to compute, in parallel, all divisors of an n-bit integer.

Lines required in a wiring diagram are proportional to n.

Execution time is proportional to the square of n.

Today I read a paper titled “Locally connected spanning trees on graphs”

The abstract is:
A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$.

The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.