bluuebunny/crossref_metadata_2025 huggingface dataset:
V. Mechanism of Superconductivity
Authors: Matsuno Shunichi , Ushio Hideki , Suwa Yuji , Kamimura Hiroshi
Published: October 2003

A possibility of phonon-mediated interaction as a mechanism of high- T c superconductivity is discussed. Because of different spatial distribution of Bloch wave function for up-spin particle and down-spin particle in the present model, the effective pair interaction which is derived from electron–phonon interaction is shown to have significant momentum- transfer dependence that is quite different from ordinary phonon-mediated interaction. This characteristic of pair interaction together with the geometric feature of Fermi-surface derived in a previous paper III leads to a dx2-y2 symmetric gap state which is consistent with experimental results. Since d-wave state has much smaller Coulomb repulsion term than s-wave state, strong electron-phonon coupling in the present model is expected to cause the occurrence of high-temperature superconductivity. However, in the present model, it is shown that a factor that reduces superconducting transition temperature appear as a result of a fluctuation effect of antiferromagnetic (AF) order of localized Cu spins. The factor λs which should be proportional to AF correlation length λ AF , determines the time scale τs which eliminates the contribution from the retarded effective pair interaction of time argument larger than τs. Existence of length scale λs explains why T c goes to zero as increasing hole carrier to some extent, and why non-magnetic impurity such as Pb reduces T c strongly. λs also explains the finite density of zero-gap states observed in overdoped regime or samples with non-magnetic impurities.
A Comparative Study of Different Tunnel Barriers for C-Axis Oriented Y(Ho)Ba2Cu3O7 Based Trilayer Structures
Authors: Cucolo A. M. , Prieto P.
Published: October 2003

We report on the structural and electrical characterization of c-axis oriented Y(Ho)Ba2Ca3O7 -based trilayer structures with different insulating layers. A comparative study of Y2O3 , SrTiO3 and PrBa2Cu3O7 barriers is carried out. Structural characterization demonstrates the epitaxial growth of the heterostructures with sharp interfaces between the different layers. Resistivity and ac susceptibility dependences on temperature indicate no degradation of the superconducting properties of the bottom and top electrodes. Josephson effect and quasi-particle tunneling are observed in the YBa2Cu3O7/Y2O3/YBa2Cu3O7 structures. The best conductance characteristics are obtained for YBa2Cu3O7/PrBa2Cu3O7/HoBa2Cu3O7 trilayers that show quasi-ideal S-I-S behavior. Well defined maxima at ± 45 mV and a zero-bias conductance less than 5% of the normal state value are measured in these junctions.
Evolution of Spectral Functions in Doped Transition Metal Oxides
Authors: Kajueter H. , Kotliar G. , Sarma D. D. , Barman S. R.
Published: October 2003

We discuss the experimental photoemission and inverse photoemission of early transition metal oxides, in the light of the dynamical mean field theory of correlated electrons which becomes exact in the limit of infinite dimensions. We argue that a comprehensive description of the experimental data requires spatial inhomogeneities and present a calculation of the evolution of the spectral function in an inhomogeneities and present a calculation of the evolution of the spectral function in an inhomogenous system with various degrees of inhomogeneity. We also point out that comparison of experimental results and large d calculations require that the degree of correlation and disorder is larger in the surface than in the bulk.
Low Power Design for Wireless RF Transceiver–An Industrial View
Authors: Wang Nan-Lei , Adam Douglas
Published: October 2003

In recent years, wireless communication in the radio frequency has a rapid growth, most noticeably the cellular phone. Analog FM systems, such as AMPS and TACS, have won a great success. In the 90s, digital systems appear, such as GSM in Europe, IS54/136 and IS95 in US, and PDC in Japan. Most recently, PCS draws the attention; there are many standards proposed around the world and they all use digital modulation schemes. With the ISM bands at 900 MHz and 2.4 MHz, many other innovative application will become possible.

Unlike the computer such RF wireless gadgets contain one peculiar subsystem: the RF transceiver. The RF transceiver translates the baseband voice and data to and from a radio frequency signal which is emitted and received by antennae. Each system specifies the operation frequency, the transmit power, the receiver sensitivity, and the signal quality. The RF transceiver must satisfy all these requirements.

As technology progresses, portable product becomes the dominant one which relies on the rechargeable battery. To maintain a decent talk time standby time, the completed product must be designed with low power consumption in mind. In the portable cellular phone the RF transceiver faces the greatest challenge in the low power design since it is the most power hungry portion: the transmitter consumes 90% power during transmission in the FM cellular phone nowadays.

To achieve low power consumption of the RF transceiver, the designer has to work to:

(1) transceiver architecture to reduce parts count and therefore power comsumption.

(2) selection/design the lowest power comsumption IC/module for a given function block.

(3) maintain competitive pricing and small size.

In this article, FM system will be used as the baseline example to illustrate the importance of the RF transceiver in low power application. The RF transceiver architecture is described first, followed by the introduction to each function block. State-of-the-art products for each function block will be referred to. Theorectical limit of power consumption for each block will be discussed. Impact from digital modulation on RF circuit design will be reviewed as well.
Power Estimation and Power Noise Analysis for CMOS Circuits
Authors: Deng An-Chang
Published: October 2003

Power consumption is a primary concern for today's IC designers. However, determining an IC's power consumption is a difficult task, as consumption varies according to input stimulus conditions. This paper will focus on (1) the principal phenomena involved in the power consumption of CMOS circuits, (2) a brief survey of power estimation techniques, and (3) the effect of power-supply noise on circuit performance plus possible solutions to this problem.
Power-Area Trade-Offs in Divided Word Line Memory Arrays
Authors: Chang Meng-Fan , Irwin Mary Jane , Owens Robert Michael
Published: October 2003

Since on-chip caches account for a significant portion of the power budget of modern microprocessors, low power caches are needed in microprocessors destined for portable electronic applications. A significant portion of the power consumption of caches comes from accessing the cache memory array and most of the power consumption of the memory array comes from driving the bit line pairs (i.e., the column current). Various memory array architectures have been proposed to improve the word line delay and the column current. For example, in a divided word line memory array memory cells in each row are organized into blocks. Only the memory cells which are in the activated block have their bit line pairs driven, thus both improving the speed (by decreasing the word line delay) and lowering the power consumption (by decreasing the column current).

In this paper we analyze the power-area tradeoffs of divided word line memories with different size blocks. We compare the area and power consumption of 16 Kbit and 64 Kbit memory arrays with 2, 4, 8, and 16 memory cells per block. Our experiments show that a divided word line memory array can lower the power consumption by 50% to 90% over a nondivided word line memory array. However, they consume more area; the area of a divided word line memory array can be 15% to 27% larger than the area of a comparable nondivided word line array. Our experiments also showed that divided word line memory arrays with two or four memory cells in a block have better power-area product than those with more than four cells per block.
Direct Pole Placement without using Observers
Authors: Janakiraman P. A. , Bhattacharyya A.
Published: October 2003

A new and direct approach to solve the pole placement problem for a given linear plant is reported in this paper. The conventional procedures involve complete identification of the plant and construction of either an Asymptotic or Kalman Filter type observer which use the estimated plant parameters. The estimated state variables are then fed back to place the poles at the desired locations. In the new method suggested in this paper, a simple model is constructed based on specified pole locations. A minimum number of coefficients related to the zeros of the plant and state feedback are determined together by a composite identification algorithm. When the plant input/output are corrupted by noise, it is possible to obtain accurate estimates of the parameters by using a periodic probing signal. The new procedure discussed involves minimum amount of computation for solving the direct pole placement problem. The core of the model itself takes the role of an observer.
Pulsed Charge Model of Fault Behavior Producing Seismic Electric Signals (SES)
Authors: Ikeya Motoji , Takaki Shunji , Matsumoto Hiroshi , Tani Atsushi , Komatsu Takahide
Published: October 2003

The electromagnetic (EM) behavior of a geological fault is postulated to follow the mathematical model of a fault in seismology that illustrates seismic EM anomalies EMAs). Charge densities, +q and -q in C/m2 are generated at a fault zone by the change in seismic stress, α as d q/ d t = -α d σ/ d t - q/∊ρ, where σ,∊ and ρ are the charge generation constants measured in C/N, dielectric constant and reisitivity of bedrocks, respectively. A fault of length, 2a, plane area, A and the displacement or rupture time, τ gives pulsed charge densities, +q(t) and -q(t), or a dipole moment of P(t) = 2aAq(t) = αM0[∊ρ/(τ - ∊ρ) - exp (-t/∊ρ)] using the earthquake moment M0. Maxwell's equations for this dipole in a conductive earth give power spectra of EM waves at diferrent distances. Seismic electric signals (SES) including the DC VAN method can be explained as EM waves. Electrons with density n in the atmosphere are accelerated by the electric field and travel a distance l. resulting in the exictation and ionization of atmospheric molecules leading to earthquake lightning (EQL). They also polarize the ionosphere by disturbing the transmission of EM waves prior to an earthquake and artificial electronic noises. The same pulsed field surprised eels and hamsters, suggesting seismic anomalous animal ehavious animal behavior (SAAB) as electro-physiological responses to the stimuli of electric pulses.
Low Bit-Rate Image Coding for Facial Movement
Authors: Takaya Kunio , Todd Reinhardt R.
Published: October 2003

A method of low bit-rate facial image coding specifically designed for the use in video telephone is presented. The basic principle for this facial image coding is to exploit the capabilities of 2D image warping techniques to generate the replica of the sender's facial expression merely by deforming a master face image, which is sent once at the beginning of the telephone call. Several parameters that describe facial expressions are monitored at the transmitter at the video frame rate of 30 frames/s, and then transmitted to the receiver using the in-band data channel. Since transmission of actual image data happens once or when another image is required, the bit-rate is much lower that that required by ordinary video image transmission. A fast bilinear mapping method for warped images, a grid mesh set over the facial image, various warping algorithms to realize head movement and facial motions with respect to eyes and mouth are discussed. This paper also compares the presented low bit-rate facial image coding to its competing methods such as MPEG and the method using a 3D facial model.
Adaptive Rate Subscriber Loop Data Transmission using Ethernet Interfaces
Authors: Takaya Norifumi , Dodds David E. , McCrosky Carl D.
Published: October 2003

The increasing demand for Internet and World Wide Web access from the home has stimulated research into finding methods of providing access at rates greater than the 33.6 kb/s offered by current computer modems. Most copper telephone pairs have bandwidth capacities much greater than the 3.4 kHz voice-band. Using this excess bandwidth it is possible to substantially exceed current modem rates. This paper describes an inexpensive and readily deployable network access technology capable of providing bit rates ranging from hundreds of kb/s to potentially greater than 1 Mb/s on existing copper telephone lines. The usable bit rate, which varies depending on the length and gauge of the wire, is adaptively determined at system start up. The results of rate adaption testing are presented, as well as the results of throughput testing when TCP is used to provide flow control across the adaptive rate transmission line. It is also shown that current IBM compatible computers are only capable of supporting data rates of slightly more than 1 Mb/s through Ethernet adaptor cards; providing access rates beyong a few Mb/s is currently unnecessary.
Design Verification of Complex Microprocessors
Authors: Yim Joon-Seo , Park Chang-Jae , Park In-Cheol , Kyung Chong-Min
Published: October 2003

As the complexity of microprocessors increases, functional verification becomes more difficult and emerges as the bottleneck of the design cycle. In this paper, we suggest a functional verification methodology, especially for compatible microprocessor designs. To guarantee perfect compatibility with previous microprocessors, we developed three C models in different abstraction levels, i.e. Polaris, MCV and StreC. An instruction behavioral level C model (Polaris) is verified using the slowed-down PC. In the implemetation of micro-architecture, a micro-operational level model (MCV) and RTL model (StreC) are co-simulated with consistency checking between these two models. The simulation speed of C models makes it possible to test the "real-world" application programs on the RTL design with a software board model (VPC). To increase the confidence level of verifications, Profiler reports the verification coverage of the test program, which is fed-back to the automatic test program generator (Pandora). The Restartability feature also helps to significantly reduce the total simulation time. Using the proposed verification methodology, we designed and verified the HK486, an Intel 80486 pin-compatible microprocessor successfully.
The Analysis of Input Queueing Techniques on a Crosspoint Packet Switch
Authors: Paik Jung Hoon , Lim Chae Tak
Published: October 2003

In this paper, an N × N input-buffered crosspoint packet switch which selects a Head of the Line, HOL, packet in contention randomly is analyzed with a new approach. The approach is based on both a Markov chain representation of the input buffer and the probability that a HOL packet is successfully served. The probability as a function of N is derived, and it makes it possible to express the average packet delay and the average number of packets in the buffer as a function of N. The new contention resolution policy based on the occupancy of the input buffer is also presented and analyzed with this same approach and the relationship between the two selection policies is analyzed.
A Performance-Oriented Circuit Partitioning Algorithm with Logic-Block Replication for Multi-FPGA Systems
Authors: Togawa Nozomu , Sato Masao , Ohtsuki Tatsuo
Published: October 2003

In this paper, we extend the circuit partitioning algorithm which we had proposed for multi-EPGA systems and present a new algorithm in which the delay of each critical signal path is within a specified upper bound imposed on it. The core of the presented algorithm is recursive bipartitioning of a circuit. The bipartitioning procedure consists of three stages: (0) detection of critical paths; (1) bipartitioning of a set of primary inputs and outputs; and (2) bipartitioning of a set of logic-blocks. In (0), the algorithm computes the lower bounds of delays for paths with path delay constraints and detects the critical paths based on the difference between the lower and upper bounds dynamically in every bipartitioning procedure. The delays of the critical paths are reduced with higher priority. In (1), the algorithm attempts to assign the primary inputs and outputs on each critical path to one chip so that the critical path does not cross between chips. Finally in (2), the algorithm not only decreases the number of crossings between chips but also assigns the logic-blocks on each critical path to one chip by exploiting a network flow technique. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it resolves almost all path delay constraints while maintaining the maximum number of required I/O blocks per chip small compared with conventional algorithms.
A New Fractional-N PLL Frequency Synthesizer
Authors: Sumi Yasuaki , Obote Shigeki , Fukui Yutaka , Tsuda Kazutoshi , Syoubu Kouichi
Published: October 2003

Recently, the speedup of lock up time is required in the Phase Locked Loop (PLL) frequency synthesizer. The fractional-N method is one of the most important techniques among the speedup methods proposed hitherto. The fractional-N programmable divider can divide not only an integer step but also a fractional one. However, the phase detector always generates the phase error pulse in every period of reference frequency and the elimination of this phase error pulse seems to be difficult. In this paper, a new fractional-N programmable divider is proposed. In this divider, the width of phase error pulse is decreased by introducing the new division ratio (N + 1/2) besides N and (N + 1). Then, the width of maximum phase error pulse in the new fractional-N programmable divider is less than or equal to half of that of the conventional one.
Single Chip Implementation of Encoder-Decoder for Low Bit Rate Visual Communication
Authors: Miyanohana Koji , Fujita Gen , Yanagida Kazuhiro , Onoye Takao , Shirakawa Isao
Published: October 2003

A single chip encoder-decoder dedicated to low bit rate visual communication is proposed, with the main theme focused on the object extraction and vector quantization. New schemes are introduced into an edge detector so as to extract objects by means of the block-level edge detection in conjunction with the pel-level edge detection and into a PE (Processing Element) array so as to be shared by the vector quantizer and the motion estimator. Owing to sophisticated architectures, these CODEC facilities have been implemented in 72.24 mm2 by a 0.6 μm triple-metal CMOS technology, which can enable the visual communication of QCIF (176 × 144) 10 fps pictures at a bit rate of 32 Kbps or less. The designed encoder-decoder operates at 10 MHz, and dissipates 147 mW from a single 3.3 V supply.
A Low Power Receiver Architecture for 4 Mbps Infrared Wireless Communication
Authors: Okuhata Hiroyuki , Uno Hiroshi , Kumatani Keiji , Shirakawa Isao , Chiba Toru
Published: October 2003

A high performance and low power architecture is devised for a 4 Mbps infrared wireless communication system dedicated to mobile computing. In this architecture, 4PPM (4-Pulse Position Modulation) infrared signals detected by an infrared receiver are digitized into TTL interface level pulses, and the digitized pulses are demodulated by a 1-bit digital demodulator. To extend the range of the link length, a 4PPM demodulator is synthesized to implement a demodulation algorithm which is constructed so as to accommodate the output tolerance of the infrared receiver. A part of the experimental results shows that the proposed 4 Mbps infrared communication system can achieve an error free link in the range of 0–140 cm at power consumption of 245 mW and 65 mW for transmitting and receiving, respectively. The communication controller is integrated in a 0.6 μm CMOS standard-cell chip which contains 10,015 transistors on a 12 mm2 die.
A Nonlinear Dynamics Perspective of Wolfram's New Kind of Science Part II: Universal Neuron
Authors: Chua Leon O. , Sbitnev Valery I. , Yoon Sook
Published: October 2003

Wolfram's celebrated three-input Cellular Automata is further developed and extended from the perspective of neural networks. A single explicit formula involving two nested absolute-value functions and eight adjustable parameters called synaptic weights, is presented. Such a neuron is proved to be universal by specifying the synaptic weights of all 256 local rules.

Applying the nonlinear dynamics concepts developed from Part I of this multipart series of papers, we present the rational for partitioning the entire set of 256 local rules into 16 distinct gene families, each composed of 16 gene siblings. Such a partitioning allows us to explain, if not predict, the pattern features generated from each local rule. Finally, these 16 gene families of Cellular Automata rules are encoded onto a new compact and insightful representation called the "double-helix torus."
Implementation of NOR Gate by a Chaotic Chua's Circuit
Authors: Murali K. , Sinha Sudeshna , Ditto William L.
Published: October 2003

We report the experimental implementation of the most fundamental NOR gate with a chaotic Chua's circuit by a simple threshold mechanism. This provides a proof-of-principle experiment to demonstrate the universal computing capability of chaotic circuits in continuous time systems.
Communication-Based on Topology Preservation of Chaotic Dynamics
Authors: Baptista Murilo S. , Reyes Marcelo B. , Sartorelli José C. , Grebogi Celso , Rosa Epaminondas
Published: October 2003

By using the Chua circuit we present experimental results for the feasibility of a chaotic communication scheme in which large parameter variations are allowed. The parameters are varied along special codimension one directions, on which the topology of chaotic attractors remains roughly invariant.
Hybrid Systems Forming Strange Billiards
Authors: Peters Karsten , Parlitz Ulrich
Published: October 2003

Hybrid dynamical systems consist of piecewise defined continuous time evolution processes interfaced with some logical or decision making process. These switches between different evolutions are triggered if the continuous state of the system reaches thresholds in state space. In the present work we investigate hybrid systems forming a special type of dynamical systems, so-called strange billiards. They show a rich variety of dynamical behavior including some unusual bifurcations and chaos, even if the continuous part of the system evolution is just linear. By means of Poincaré map techniques we discuss different dynamical behaviors. Applications to the simulation of manufacturing systems and consequences for their dynamical behavior are outlined.
Quantitative Determination of Abrupt Changes in Dynamical Systems: Illustration Via Identification of Seizure Termination in Generalized Tonic–Clonic Seizure EEG Data
Authors: Cellucci C. J. , Albano A. M. , Rapp P. E. , Krystal A. D.
Published: October 2003

We discuss key theoretical and practical issues related to the identification of transitions in dynamical systems in real-time. We focus on the choice of candidate measures and optimization of decision thresholds for candidate measures. To illustrate these issues we develop and test a procedure for identifying one particular transition, the end-point of seizures in two-channel electro-encephalographic data recorded during generalized tonic–clonic seizures. Data from twenty-eight seizures were available and used to develop and test the procedure in terms of the agreement between the computationally identified seizure end-point compared against the ratings of an expert clinical electroencephalographer. Generalizations to multivariate seizure onset detection and to seizure prediction are described.
A Neurobiological Theory of Meaning in Perception Part II: Spatial Patterns of Phase in Gamma EEGs from Primary Sensory Cortices Reveal the Dynamics of Mesoscopic Wave Packets
Authors: Freeman Walter J.
Published: October 2003

Domains of cooperative neural activity called "wave packets" have been discovered in the visual, auditory, and somatomotor cortices of rabbits that were trained to discriminate conditioned stimuli in these modalities. Each domain forms by a first order state transition, which strongly resembles a phase transition from vapor to liquid. In this view, raw sense data injected into cortex by sensory axons drive cortical action potentials in swarms like water molecules in steam. The increased activity destabilizes the cortex. Within 3 to 7 milliseconds of transition onset, the activity binds together into a state resembling a scintillating rain drop, which lasts ~80 to 100 milliseconds, then dissolves. Wave packets form at rates of 2 to 7/second in all sensory areas, overlapping in space and time. Results of sensory information processing are seen in spatial patterns of amplitude modulation (AM) of wave packets with carrier waves in the gamma range (20 to 80 Hz in rabbits). The AM patterns correspond to categories of CSs that the rabbits can discriminate. The patterns are found in electroencephalographic (EEG) potentials generated by dendrites and recorded with high-density electrode arrays. The state transitions by which AM patterns form are manifested in the spatial pattern of phase modulation (PM), which have the radial symmetry of a cone. The apex of a PM cone marks the site of nucleation of an AM pattern. The phase gradient gives a soft boundary condition, where the axonal delay in spread gives sufficient phase dispersion to reach the half-power level. The size of the wave packets (10 to 30 mm in diameter in rabbits) is determined largely by the conduction velocities of intracortical axons through which the neural cooperation is maintained. The findings show that significant cortical activity takes the form of mesoscopic interactions of millions of neurons in broad areas of cortex, which are more clearly detected in graded dendritic potentials than in action potentials. The distinction is analogous to the difference between statistical mechanical and thermodynamic descriptions of particle behavior. Both types of neural activity show spatial and temporal discontinuities but at distinctive scales of microns and msec versus mm and tenths of a second. The aim of measurement here is to establish the wave packet as the information carrier at the mesoscopic level in brain dynamics, comparable to the role of the action potential as the information carrier at the microscopic level in neuron dynamics.
Symbolic Analysis of High-Dimensional Time Series
Authors: Keller Karsten , Lauffer Heinz
Published: October 2003

In order to extract and to visualize qualitative information from a high-dimensional time series, we apply ideas from symbolic dynamics. Counting certain ordinal patterns in the given series, we obtain a series of matrices whose entries are symbol frequencies. This matrix series is explored by simple methods from nominal statistics and information theory. The method is applied to detect and visualize qualitative changes of EEG data related to epileptic activity.
Spatiotemporal Distributions of Unstable Periodic Orbits in Noisy Coupled Chaotic Systems
Authors: Dolan Kevin , Witt Annette , Kurths Jürgen , Moss Frank
Published: October 2003

Techniques for detecting encounters with unstable periodic orbits (UPOs) have been very successful in the analysis of noisy, experimental time series. We present here a technique for applying the topological recurrence method of UPO detection to spatially extended systems. This approach is tested on a network of diffusively coupled chaotic Rössler systems, with both symmetric and asymmetric coupling schemes. We demonstrate how to extract encounters with UPOs from such data, and present a preliminary method for analyzing the results and extracting dynamical information from the data, based on a linear correlation analysis of the spatiotemporal occurrence of encounters with these low period UPOs. This analysis can provide an insight into the coupling structure of such a spatially extended system.
Another Chemical Chaotic Attractor for Chua's Equation
Authors: Xu Wei Guo , Li Qian Shu
Published: October 2003

A new chemical kinetic system for Chua's equation is presented. In contrast to the double-scroll Chua's attractor, the chaotic attractor obtained from this system has only one scroll.
Cycling Behavior in Near-Identical Cell Systems
Authors: Palacios Antonio , Longhini Patrick
Published: October 2003

A generic pattern of collective behavior of symmetric networks of coupled identical cells is cycling behavior. In networks modeled by symmetric systems of differential (difference) equations, cycling behavior appears in the form of solution trajectories (orbits) that linger around symmetrically related steady-states (fixed points) or periodic solutions (orbits) or even chaotic attractors. In this last case, it leads to what is called "cycling chaos". In particular, Dellnitz et al. [1995] demonstrated the existence of cycling chaos in continuous-time three-cell systems modeled by Chua's circuit equations and Lorenz equations, while Palacios [2002, 2003] later demonstrated the existence of cycling chaos in discrete-time cell systems. In this work, we consider two issues that follow-up from these previous works. First of all, we address the generalization of existence of cycling behavior in continuous-time systems with more than three cells. We demonstrate that increasing the number of cells, while maintaining the same network connectivity used by Dellnitz et al. [1995], is not enough to sustain the nature of a cycle, in which only one cell is active at any given time. Secondly, we address the existence of cycling behavior in networks with near-identical cells, where the internal dynamics of each cell is governed by an identical model equation but with possibly different parameter values. We show that, under a new connectivity scheme, cycling behavior can also occur in networks with near-identical cells.
Finding a Covering Triangulation Whose Maximum Angle is Provably Small
Authors: Mitchell Scott A.
Published: October 2003

We consider the following problem: given a planar straight-line graph, find a covering triangulation whose maximum angle is as small as possible. A covering triangulation is a triangulation whose vertex set contains the input vertex set and whose edge set contains the input edge set. The covering triangulation problem differs from the usual Steiner triangulation problem in that we may not add a vertex on any input edge. Covering triangulations provide a convenient method for triangulating multiple regions sharing a common boundary, as each region can be triangulated independently.

We give an explicit lower bound γopt on the maximum angle in any covering triangulation of a particular input graph in terms of its local geometry. Our algorithm produces a covering triangulation whose maximum angle γ is provably close to γopt. Specifically, we show that [Formula: see text], i.e., our γ is not much closer to π than is γopt. To our knowledge, this result represents the first nontrivial bound on a covering triangulation's maximum angle. Our algorithm adds O(n) Steiner points and runs in time O(n log n), where n is the number of vertices of the input. We have implemented an O(n2) time version of our algorithm.
Efficient Bitmap Resemblance Under Translations
Authors: Kedem Klara , Cohen Daniel
Published: October 2003

We present three efficient algorithms for resemblance between two bitmaps. Two of the algorithms are rasterized approximations, based on existing algorithms which compute the exact minimum Hausdorff distance between point sets under translation. The minimum Hausdorff distance is a min – max – min distance. We convert this operation into an and – or – and operation. This conversion, together with the fact that we encode distances into bits in the words of the pixel plane, of standard graphics hardware, contribute to the speed-up of our rasterized algorithms. The third algorithm is faster than the first two rasterized algorithms, and combines speed-up ideas from both. The performance of our rasterized algorithm is compared to an existing rasterized approximation algorithm for bitmap resemblance. We compare runtimes of these algorithms, parametrized by the size of the bitmap, the density of black bits in the bitmap and other parameters. Our results are summarized in tables and show that our algorithm is faster.
The Floodlight Problem
Authors: Bose Prosenjit , Guibas Leonidas , Lubiw Anna , Overmars Mark , Souvaine Diane , Urrutia Jorge
Published: October 2003

Given three angles summing to 2π, given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains ki of the points. This new result on dissecting point sets is used to prove that lights of specified angles not exceeding π can be placed at n fixed points in the plane to illuminate the entire plane if and only if the angles sum to at least 2π. We give O(n log n) algorithms for both these problems.
Convex Grid Drawings of 3-Connected Planar Graphs
Authors: Chrobak Marek , Kant Goos
Published: October 2003

We consider the problem of embedding the vertices of a plane graph into a small (polynomial size) grid in the plane in such a way that the edges are straight, nonintersecting line segments and faces are convex polygons. We present a linear-time algorithm which, given an n-vertex 3-connected plane G (with n ≥ 3), finds such a straight-line convex embedding of G into a (n - 2) × (n - 2) grid.
Approximating Convex Polyhedra with Axis-Parallel Boxes
Authors: Zhu Binhai
Published: October 2003

In this paper, we present an O(n4 log 2n) time algorithm to compute an approximate discrete axis-parallel box of a given n-vertex convex polyhedron P such that the given polyhedron is minimized. Here, "discrete" means that each plane containing a face of the approximate box passes through a vertex of P (or, more generally, passes through a point of a set of given points). This algorithm is significantly faster than the brute force O(n7) time solution for computing the optimal approximate axis-parallel box A* of P such that the symmetric difference of the volume between P and A* is minimized. We present a linear time algorithm to compute a pseudo-optimal (with factor [Formula: see text] approximate axis-parallel box of a convex polyhedron under the Hausdorff distance criterion. We also present O(n) and O(n7 log n) time algorithms to compute the optimal approximate ball, with or without a fixed center, of a convex polyhedron under the Hausdorff distance criterion.
A Fast Algorithm for Constructing Sparse Euclidean Spanners
Authors: Das Gautam , Narasimhan Giri
Published: October 2003

Let G = (V,E) be a n-vertex connected graph with positive edge weights, and let t > 1 be a real constant. A subgraph G' is a t-spanner if for all u,v ∊ V, the weight of the shortest path between u and v in G' is at most t times the weight of the corresponding shortest path in G. We design an O(n log 2 n) time algorithm which, given a set V of n points in k-dimensional space (for any fixed k), and any real constant t > 1, produces a t-spanner of the complete Euclidean graph of V. This algorithm retains the spirit of a recent O(n3 log n) time greedy algorithm which produces t-spanners; we use graph clustering techniques to achieve a more efficient implementation. Our spanners have O(n) edges and weight O(1)· wt(MST), which is similar to the size and weight of spanners constructed by the greedy algorithm. The constants implicit in the O-notation depend upon t and k.
Matching Shapes with a Reference Point
Authors: Aichholzer Oswin , Alt Helmut , Rote Günter
Published: October 2003

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets.

The focus of our paper is the general study of reference points (like the Steiner point) and their properties with respect to shape matching.

For more general transformations than just translations, our method eliminates several degrees of freedom from the problem and thus yields good matchings with improved time bounds.
Computational Geometry Column 31
Authors: O'Rourke Joseph
Published: October 2003

Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing k-flats in dimension d.
Improved Computation of Optimal Rectilinear Steiner Minimal Trees
Authors: Ganley Joseph L. , Cohoon James P.
Published: October 2003

This paper presents two new algorithms for computing optimal rectilinear Steiner minimal trees. The first algorithm is a simple, easily implemented dynamic programming algorithm that computes an optimal rectilinear Steiner minimal tree on n points in O(n3n) time. The second algorithm improves upon the first using the concept of full-set screening and runs in at most O(n22.62n) time. The analysis of the second algorithm includes a proof that there are at most O(n 1.62n) full sets on n terminals. For instances small enough to practically solve, these time bounds are provably better than the best known bounds of any previous algorithm. Experimental evidence is presented that demonstrates that the algorithms are fast in practice as well. The paper also includes a brief survey of previous algorithms for computing optimal rectilinear Steiner minimal trees.
Faster Circle Packing with Application to Nonobtuse Triangulation
Authors: Eppstein David
Published: October 2003

We show how to pack a non-simple polygon with O(n) tangent circles, so that the union of the polygon boundary components and circles is connected, in total time O(n log n). This improves a previous O(n log 2 n) bound. By combining this with methods of Bern, Mitchell, and Ruppert we can extend this to a circle packing in which each portion of the polygon outside the circles is adjacent to at most four circles or boundary edges, and as a consequence we can triangulate the polygon with right and acute triangles, using O(n) Steiner points, again in the same O(n log n) time bound.
Computing Visibility Information in an Inaccurate Simple Polygon
Authors: Cai Leizhen , Mark Keil J.
Published: October 2003

This paper is concerned with the problem of capturing meaningful and useful visibility information inside a simple polygon given only an inaccurate representation of the vertices of the polygon. We introduce a notion of a visibility skeleton of an inaccurate representation of a simple polygon. We show that in most cases the visibility skeleton of a representation can be computed efficiently; furthermore, the visibility skeleton can be used to plan a collision-free path inside the polygon whose length approximates the length of a shortest such path to within a constant factor (independent of the number of vertices in the polygon).
Computing a Largest Empty Anchored Cylinder, and Related Problems
Authors: Follert Frank , Schömer Elmar , Sellen Jürgen , Smid Michiel , Thiel Christian
Published: October 2003

Let S be a set of n points in ℝd, and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin) such that min p ∈ s w(p) · d(p,R) ( resp. min p ∈ S w(p) · d(p,l)) is maximal. If all weights are one, this corresponds to computing a silo emanating from the origin ( resp. a cylinder whose axis contains the origin) that does not contain any point of S and whose radius is maximal. For d = 2, we show how to solve these problems in O(n log n) time, which is optimal in the algebraic computation tree model. For d = 3, we give algorithms that are based on the parametric search technique and run in O(n log 4 n) time. The previous best known algorithms for these three-dimensional problems had almost quadratic running time. In the final part of the paper, we consider some related problems.
Rational Quadratic Parameterizations of Quadrics
Authors: Wang Wenping , Joe Barry , Goldman Ronald
Published: October 2003

Every irreducible quadric in E3 has infinitely many different rational quadratic parameterizations. These parameterizations and the relationships between them are investigated. It is shown that every faithful rational quadratic parameterization of a quadric can be generated by a stereographic projection from a point on the quadric, called the center of projection (COP). Two such parameterizations for the same quadric are related by a rational linear reparameterization if they have the same COP; otherwise they are related by a rational quadratic reparameterization. We also consider unfaithful parameterizations for which, in general, a one-to-one correspondence between points on the surface and parameters in the plane does not exist. It is shown that all unfaithful rational quadratic parameterizations of a properly degenerate quadric can be characterized by a simple canonical form, and there exist no unfaithful rational quadratic parameterizations for a nondegenerate quadric. In addition, given a faithful rational quadratic parameterization of a quadric, a new technique is presented to compute its base points and inversion formula. These results are applied to solve the problems of parameterizing the intersection of two quadrics and reparameterizing a given quadric parameterization with respect to a different COP without implicitization.
Logic Grammars for Diagnosis and Repair
Authors: Christiansen Henning , Dahl Veronica
Published: October 2003

We propose an abductive model based on Constraint Handling Rule Grammars (CHRGs) for detecting and correcting errors in problem domains that can be described in terms of strings of words accepted by a logic grammar. We provide a proof of concept for the specific problem of detecting and repairing natural language errors, in particular, those concerning feature agreement. Our methodology relies on grammar and string transformation in accordance with a user-defined dictionary of possible repairs. This transformation also serves as top-down guidance for our essentially bottom-up parser. With respect to previous approaches to error detection and repair, including those that also use constraints and/or abduction, our methodology is surprisingly simple while far-reaching and efficient.
Is Error-Based Pruning Redeemable?
Authors: Hall Lawrence O. , Bowyer Kevin W. , Banfield Robert E. , Eschrich Steven , Collins Richard
Published: October 2003

Error based pruning can be used to prune a decision tree and it does not require the use of validation data. It is implemented in the widely used C4.5 decision tree software. It uses a parameter, the certainty factor, that affects the size of the pruned tree. Several researchers have compared error based pruning with other approaches, and have shown results that suggest that error based pruning results in larger trees that give no increase in accuracy. They further suggest that as more data is added to the training set, the tree size after applying error based pruning continues to grow even though there is no increase in accuracy. It appears that these results were obtained with the default certainty factor value. Here, we show that varying the certainty factor allows significantly smaller trees to be obtained with minimal or no accuracy loss. Also, the growth of tree size with added data can be halted with an appropriate choice of certainty factor. Methods of determining the certainty factor are discussed for both small and large data sets. Experimental results support the conclusion that error based pruning can be used to produce appropriately sized trees with good accuracy when compared with reduced error pruning.
An Agent-Based Approach to Inference Prevention in Distributed Database Systems
Authors: Tracy James , Chang Liwu , Moskowitz Ira S.
Published: October 2003

We propose an inference prevention agent as a tool that enables each of the databases in a distributed system to keep track of probabilistic dependencies with other databases and then use that information to help preserve the confidentiality of sensitive data. This is accomplished with minimal sacrifice of the performance and survivability gains that are associated with distributed database systems.
Actions with Duration and Constraints: The Ramification Problem in Temporal Databases
Authors: Papadakis Nikos , Plexousakis Dimitris
Published: October 2003

The ramification problem is a hard and ever present problem in systems exhibiting a dynamic behavior. The area of temporal databases in particular is still lacking satisfactory solutions to the ramification problem. In this paper, we address the ramification problem based on causal relationships that take time into account. We study the problem for both instantaneous actions and actions with duration. The proposed solution advances previous work by considering actions with effects occurring in any of the possible future situations resulting from an action's execution.
Quantization of an Integrable Minisuperspace Model in Dilaton-Einstein Gravity
Authors: Cavaglià Marco , de Alfaro Vittorio
Published: October 2003

We quantize the minisuperspace model of Einstein gravity plus dilaton that describeseither a static spherically symmetric configuration or a Kantowski–Sachs like universe. We develop the canonical formalism and identify canonical quantities that generate rigid symmetries of the Hamiltonian. Quantization is performed both by the Dirac and the reduced methods. Since the system is classically integrable we show that both approaches lead to the same positive definite Hilbert space.
The Interstellar Medium as a Gravity Wave Detector
Authors: Fakir Redouane
Published: October 2003

An observer, situated several thousand light-years away from a radio pulsar, finds himself embedded in the diffraction pattern resulting from the propagation of the radio waves through the irregular interstellar medium. The gravity waves produced by an intervening binary star cause the diffraction pattern to be displaced laterally in a manner familiar from refractive interstellar scintillation, except that this gravity wave effect is not dispersive. This periodic displacement can reach a few hundred kilometers. Thus, there seems to be a possibility that the exceedingly faint gravity waves can manifest themselves macroscopically.
On the Black-Hole Kink
Authors: González-Díaz Pedro F.
Published: October 2003

By allowing the light cones to tip over on hypersurfaces according to the conservation laws of an one-kink in static, Schwarzschild black-hole metric, we show that in the quantum regime there also exist instantons whose finite imaginary action gives the probability of occurrence of the kink metric corresponding to single chargeless, nonrotating black holes taking place in pairs, the holes of each pair being joined on an interior surface, beyond the horizon.