1.
Computing Conformal Invariants: Period Matrices - Gu
, Xianfeng; Wang
, Yalin; Yau
, Shing-Tung
This work introduces a system of algorithms to compute period matrices for general
surfaces with arbitrary topologies. The algorithms are intrinsic to the geometry, and independent of
surface representations. The computation is efficient, stable and practical for real applications. The
algorithms are experimented on real surfaces including human faces and sculptures, and applied to
surface identification problems. It is the first work that is both theoretically solid, and practically
robust and accurate to handle real surfaces with arbitrary topologies.
2.
Geometric Compression Using Riemann Surface Structure - Gu
, Xianfeng; Wang
, Yalin; Yau
, Shing-Tung
This paper introduces a theoretic result that shows any surface in 3 dimensional Euclidean space can
be determined by its conformal factor and mean curvature uniquely up to rigid motions. This theorem disproves the
common belief that surfaces have three functional freedoms and immediately shows that one third of geometric data
can be saved without loss of information. ¶
The paper develops a practical algorithm to losslessly compress geometric surfaces based on Riemann surface
structures. First we compute a global conformal parameterization of the surface. The surface can be segmented by
holomorphic flows, where each segment can be conformally mapped to a rectangle on the parameter...
3.
A Nash Equilibrium related to the Poisson Channel - Harremoës
, P.; Vignat
, C.
An information theoretical game is considered where both signal and noise are
generalized Bernoulli sums with upper bounds on their mean values. It is shown that a pair of
Poisson distributions is a Nash equilibrium pair.
4.
Volumetric Harmonic Map - Wang
, Yalin; Gu
, Xianfeng; Yau
, Shing-Tung
We develop two different techniques to study volume mapping problem in Computer Graphics and
Medical Imaging fields. The first one is to find a harmonic map from a 3 manifold to a 3D solid sphere and the
second is a sphere carving algorithm which calculates the simplicial decomposition of volume adapted to surfaces.
We derive the 3D harmonic energy equation and it can be easily extended to higher dimensions. We use a textrehedral
mesh to represent the volume data. We demonstrate our method on various solid 3D models. We suggest that 3D
harmonic mapping of volume can provide a canonical coordinate system for feature identification...
5.
A Stepwise Approximation of Intractable Spatial Constraints in Image Queries - Zhang
, QingLong; Yau
, Stephen S.T.
An image stored in image database systems is assumed to be associated with some content-based
meta-data about that image, that is, information about objects in the image and absolute/relative spatial relationships
among them. An image query for such an image database system can generally be handled in two ways: exact
picture matching and approximate picture matching. We address the approximate picture matching problem of
central interest in this paper, and present a stepwise approximation of intractable spatial constraints in an image
query. Especially, this stepwise approximation may be pre-processed on an image query before an advanced picture
matching algorithm is invoked. We then work out details...
7.
Operations on Rigid Formations of Autonomous Agents - Eren, Tolga; Anderson, Brian D. O.; Morse, A. Stephen; Whiteley, Walter; Belhumeur, Peter N.
This paper is concerned with the maintenance of rigid formations
of mobile autonomous agents. A key element in all future
multi-agent systems will be the role of sensor and communication
networks as an integral part of coordination. Network topologies
are critically important for autonomous systems involving mobile
underwater, ground and air vehicles and for sensor networks. This
paper focuses on developing techniques and strategies for the
analysis and design of sensor and network topologies required
to achieve a rigid formation for cooperative tasks. Energy
efficiency and communication bandwidth are critically important
in formations of mobile autonomous agents, and hence strategies
that make efficient use of power and energy are beneficial.
Therefore, we...
8.
Peformance Analysis Conditioned on Rare Events: An
Adaptive Simulation Scheme - Borkar, V. S.; Juneja, S.; Kherani, A. A.
We consider the problem of simulation-based estimation of
performance measures for a Markov chain conditioned on a rare
event. The conditional law depends on the solution of a
multiplicative Poisson equation. An adaptive scheme for learning
the latter is proposed and analyzed. An example motivated by a
well known problem in communication networks is given.
Applications of the basic scheme to other related domains such
as importance sampling for rare event simulation and the
solution of a class of eigenvalue problems are also sketched.
9.
A Performance Analysis of the 802.11 Wireless Lan Medium
Access Control - Gupta, Nitin; Kuman, P. R.
We study the performance of the IEEE 802.11 protocol. We
present an extension of a methodology for the collocated
one-hop case which allows the incorporation of channel
errors. The results closely agree with simulation results.
A delay analysis is also presented. We also present an
extension of this methodology to the multi-hop case with
non-collocated nodes. The approach uses specific topology
dependent relations. Specific results are presented for
the ring and mesh topologies, and compared against
simulation results.
10.
Combination Exchange Mechanisms for Efficient Bandwidth Allocation - Jain, Rahul; Varaiya, Pravin P.
The size, scale and multiple ownership of communication network
resources makes it important to consider an economic framework
wherein we can investigate the efficiency of network operation
taking agents' incentives into account. Such a framework has
been considered in the design and analysis of pricing mechanisms
to regulate congestion and share bandwidth over short time scales.
We consider time scales of a few months over which owners of
communication links lease bandwidth to network service providers.
As is well-known, economic efficiency is related to how close an
allocation is to a competitive equilibrium. We first show that
achieving economic efficiency through a market mechanism depends
on network topology. We then show...
11.
A "Small World" Approach to Heterogeneous Networks - Reznik, Alex; Kulkarni, Sanjeev R.; Verdu, Sergio
We consider a heterogeneous (also called "hybrid") ad-hoc network
with wired and wireless links. This type of network was previously
considered by Kulkarni and Viswanath in [9] where achievable
transport capacity growth rates were demonstrated for a structured
wired infrastructure. The present paper improves on this work by
demonstrating that efficiency can be increased significantly if
the wired links are introduced at random.
12.
Natural Resolution of Ill-Posedness of Inverse Kinematics
for Redundant Robots Under Constraints - Arimoto, S.; Bae, J.-H.; Hashiguchi, H.; Ozawa, R.
In order to enhance dexterity in execution of robot tasks, a
redundant number of degrees-of-freedom (DOF) is adopted for
design of robotic mechanisms like robot arms and multi-fingered
robot hands. Associated with such redundancy in DOFs relative
to the number of physical variables necessary and sufficient
for description of a given task, an extra performance index
is introduced for controlling such a redundant robot in order
to avoid arising of ill-posedness of inverse kinematics from
the task space to the joint space. This paper shows that such
an ill-posedness problem of DOF redundancy can be resolved in
a natural way on the basis of construction of sensory feedback
signals from the...
13.
The New Family of Cracked Sets and the Image Segmentation
Problem Revisited - Delfour, Michel C.; Zolesio, Jean-Paul
The object of this paper is to introduce the new family of
cracked sets which yields a compactness result in the W
1,p-topology associated with the oriented distance
function and to give an original application to the celebrated
image segmentation problem formulated by Mumford and Shah
[21]. The originality of the approach is that it does not require a
penalization term on the length of the segmentation and that,
within the set of solutions, there exists one with minimum density
perimeter as defined by Bucur and Zolesio in [3]. This theory can
also handle N-dimensional images. The paper is completed with
several variations of the problem with or without a...
14.
Chaotic Quantized Feedback Stabilizers: The Scalar Case - Fagnani, Fabio
In this paper we consider practical stabilization strategies of
scalar linear systems by means of quantized feedback maps which
use a minimal number of quantization levels. These stabilization
schemes are based on the chaotic properties of piecewise affine
maps and their performance can be analyzed in terms of the mean
time needed to shrink the system from an initial interval into a
fixed target interval. We show here that this entrance time grows
linearly with respect to the contraction rate defined as the quotient
of the length of the initial and target interval respectively.
Estimations are obtained using denumerable Markov chains arguments.
15.
Model Calculations for Joint Pattern Recognition and Signal
Reconstruction in Cyro Electron Microscopy - Yin, Zhye; Doerschuk, Peter C.; Gelfand, Saul B.
Cryo electron microscopy is a measurement modality which provides
images from which 3-D reconstructions of biological particles such
as viruses can be estimated. When the specimen is composed of mixtures
of particles of different types, the 3-D reconstruction problem must
be solved jointly with a pattern classification problem. The performance
of the estimators is not well understood because the computations are
not suitable for analytical results and are too large for extensive
Monte Carlo results. The problem formulation typically has nuisance
parameters and different treatments of the nuisance parameters lead
to different estimators. In this paper two types of estimators and
two model problems are studied with the conclusion that...
16.
A Regularized Solution to the Birkhoff Interpolation Problem - Zhou, Y.; Martin, C. F.
In this paper a relationship between the Birkhoff interpolation
problem and the problem of control theoretic splines is established.
It is shown that the Birkhoff interpolation problem has a solution
if and only if a certain cost function remains bounded under
perturbation of a suitably chosen variable.
17.
Fixed Points and Stability of Density Evolution - Richardson, Tom; Urbanke, Rudiger
Density evolution is a dynamic system in a space of probability
distributions representing the progress of iterative decoders in
the infinite block length limit. In this paper we establish some
basic results concering this process. In particular we show that
the decoding threshold is equivalent to to appearance of non-trivial
fixed point solutions to the density evolution equations. In the
case of LDPC codes we prove the sufficiency of the previously
published stability condition for stability of the DELTAINFINITY
fixed point and slightly strengthen the necessity result.
18.
Optimal Global Conformal Surface Parameterization for Visualization - Jin, Miao; Wang, Yalin; Gu, Xianfeng; Yau, Shin-Tung
All orientable metric surfaces are Riemann surfaces and admit
global conformal parameterizations. Riemann surface structure
is a fundamental structure and governs many natural physical
phenomena, such as heat diffusion, electric-magnetic fields on
the surface. Good parameterization is crucial for simulation
and visualization. This paper gives an explicit method for
finding optimal global conformal parameterizations of arbitrary
surfaces. It relies on certain holomorphic differential forms
and conformal mappings from differential geometry and Riemann
surface theories. Algorithms are developed to modify topology,
locate zero points, and determine cohomology types of differential
forms. The implementation is based on finite dimensional optimization
method. The optimal parameterization is intrinsic to the geometry,
preserving angular structure, and can play...
19.
Throughput of Q-Ary Splitting Algorithms for Contention Resolution
in Communication Networks - Houdt, B.; Blondia, C.
The throughput characteristics of contention-based random access
channels which use Q-ary splitting algorithms (where Q
is the number of groups into which colliding users are split) are
analyzed. The algorithms considered are of the Capetanakis-Tsybakov-
Mikhailov-Vvedenskaya (CTMV) type and are studied for infinite
populations of identical users generating packets according to a
discrete time batch Markovian arrival process (D-BMAP). D-BMAPs
are a class of tractable Markovian arrival processes, which, in
general, are non-renewal. Free channel-access is assumed in
combination with Q-ary collision resolution algorithms that
exploit either binary or ternary feedback. For the resulting schemes,
tree structured Quasi-Birth-Death (QBD) Markov chains are constructed
and their stability is determined. The maximum achievable throughput
is...
20.
Surface Segmentation Using Global Conformal Structure - Wang, Yalin; Gu, Xianfeng; Yau, Shing-Tung
Surface segmentation is a fundamental problem in computer graphics.
It has various applications such as metamorphosis, surface matching,
surface compression, 3D shape retrieval, texture mapping, etc. All
orientable surfaces are Riemann surfaces, and admit conformal structures.
This paper introduces a novel surface segmentation algorithm based on
its conformal structure. Each segment can be conformally mapped to a
planar rectangle, and the transition maps are planar translations.
The segmentation is intrinsic to the surface, independent of the embedding,
and consistent for surfaces with similar geometries. By using segmentation
based on conformal structure, the mapping between surfaces with arbitrary
topologies can be constructed explicitly. The method is rigorous, efficient
and automatic. The segmentation...
1.
