Archives for 2003

Today I read a paper titled “Computer-Generated Photorealistic Hair”

The abstract is:
This paper presents an efficient method for generating and rendering photorealistic hair in two dimensional pictures.

The method consists of three major steps.

Simulating an artist drawing is used to design the rough hair shape.

A convolution based filter is then used to generate photorealistic hair patches.

A refine procedure is finally used to blend the boundaries of the patches with surrounding areas.

This method can be used to create all types of photorealistic human hair (head hair, facial hair and body hair).

It is also suitable for fur and grass generation.

Applications of this method include: hairstyle designing/editing, damaged hair image restoration, human hair animation, virtual makeover of a human, and landscape creation..

Today I read a paper titled “The Risk Profile Problem for Stock Portfolio Optimization”

The abstract is:
This work initiates research into the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit.

The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown.

The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market.

For portfolios made up of two stocks, this work shows how to exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem.

However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem.

In particular, it is #P-complete to compute the distribution function associated with the average-case bound.

On the positive side, approximate answers can be computed by using random sampling techniques similar to those for high-dimensional volume estimation.

When k>2 stocks are considered, it is proved that a simple solution based on the same flow concepts as the 2-stock algorithm would imply that P = NP, so is highly unlikely.

This work gives approximation algorithms for this case as well as exact algorithms for some important special cases.

Today I read a paper titled “Behaviour-based Knowledge Systems: An Epigenetic Path from Behaviour to Knowledge”

The abstract is:
In this paper we expose the theoretical background underlying our current research.

This consists in the development of behaviour-based knowledge systems, for closing the gaps between behaviour-based and knowledge-based systems, and also between the understandings of the phenomena they model.

We expose the requirements and stages for developing behaviour-based knowledge systems and discuss their limits.

We believe that these are necessary conditions for the development of higher order cognitive capacities, in artificial and natural cognitive systems.

Today I read a paper titled “Towards a Theory of Cache-Efficient Algorithms”

The abstract is:
We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters.

Our model, an extension of Aggarwal and Vitter’s I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations.

As a corollary, we obtain cache-optimal algorithms for some fundamental problems like sorting, FFT, and an important subclass of permutations in the single-level cache model.

We also show that ignoring associativity concerns could lead to inferior performance, by analyzing the average-case cache behavior of mergesort.

We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting.

Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and dealing with the hitherto unresolved problem of limited associativity.

Today I read a paper titled “Map Graphs”

The abstract is:
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires).

Such adjacencies define a map graph.

We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point.

Today I read a paper titled “Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees”

The abstract is:
In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights.

The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time.

The first part of the paper surveys various algorithms available today both in sequential and distributed environments to solve static MST problem.

We also present some of the efficient sequential algorithms for computing dynamic MST like the Frederickson’s algorithm and Eppstein’s sparsification technique.

Lastly we present our new sequential and distributed algorithms for dynamic MST problem.

To our knowledge, this is the first of the distributed algorithms for computing dynamic MSTs.

Today I read a paper titled “Verbal Interactions in Virtual Worlds”

The abstract is:
We first discuss respective advantages of language interaction in virtual worlds and of using 3D images in dialogue systems.

Then, we describe an example of a verbal interaction system in virtual reality: Ulysse.

Ulysse is a conversational agent that helps a user navigate in virtual worlds.

It has been designed to be embedded in the representation of a participant of a virtual conference and it responds positively to motion orders.

Ulysse navigates the user’s viewpoint on his/her behalf in the virtual world.

On tests we carried out, we discovered that users, novices as well as experienced ones have difficulties moving in a 3D environment.

Agents such as Ulysse enable a user to carry out navigation motions that would have been impossible with classical interaction devices.

From the whole Ulysse system, we have stripped off a skeleton architecture that we have ported to VRML, Java, and Prolog.

We hope this skeleton helps the design of language applications in virtual worlds.