bluuebunny/crossref_metadata_2025 huggingface dataset:
Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
Authors: Manacher Glenn K. , Mankus Terrance A.
Published: October 2003

A maximum clique is sought in a set of n proper circular arcs (PCAS). By means of several passes, each O(n) in time and space, a PCAS is transformed initially into a set of circle chords and finally into a set of intervals. This interval model inherits a special property from the PCAS which ensures the discovery of a maximum overlap clique in time O(n). The one-to-one arc/interval correspondence guarantees the identification of the maximum clique in the PCAS in O(n) time and space.

The present paper gives new, simpler proofs for the lemmas first outlined by us in Ref. [9], extending the methods outlined in that paper so that the time bound is improved from O(n log n) to O(n). The method depends only on certain interconnections between constructions related to the computation of longest increasing subsequences.

Independently, Hell, Huang and Bhattacharya5 recently discovered a completely different approach that also achieves the same complexity, and can moreover be applied to the weighted case and to the coloring problem on proper circular arcs. The previous best result, due to Apostolico and Hambrusch2 applies to general circular arc models and has time complexity O(n2 log log n) and space complexity O(n).

As applications of the method, we show that maximum weight clique of a set of weighted proper circular arcs can be found in time O(n2) and space O(n). The previous best result was O(n2 log log n) for dense general circular arc graphs.13 We also show that, for n chords with randomly placed endpoints (1) the average cardinality of a maximum clique is cn1/2 ± o(n1/2), where 21/2< c < e21/2, and (2) a maximum clique may be found in average time O(n3/2) and space θ(n). The previous best average time complexity, derived from Ref. [1], was O(n3/2 log n).
Signal Compression
Authors: Jayant Nikil
Published: October 2003

This article is an introduction to a special issue on signal coding and compression. We begin by defining the concepts of digital coding and audiovisual signal compression. We then describe the four dimensions of coding performance: bit rate, signal quality, processing delay and complexity. We illustrate the two basic principles of audiovisual coding, removal of signal redundancy and the matching of the quantizing system to the properties of the human perceptual system, with specific recent examples of coding algorithms. We then summarize standards for, and applications of audiovisual signal compression. A fast-emerging application is the internetworking of audiovisual information, a field that is too recent to be covered in the articles in this collection. We conclude our article by presenting our views about future research directions in the field.
Fiber Optic Infrastructure for Wireless Communication Networks
Authors: Lau Kam Y. , Cutrer David M. , Georges John B. , Yeung Simon
Published: October 2003

It is clear that to meet the new demands of wireless customers, conventional cellular service providers and upcoming Personal Communication Service (PCS) providers for conventional phone service and high bandwidth wireless LAN must upgrade their networks to provide complete radio coverage. This evolution has motivated the need for low-cost systems that transport radio signals to and from areas of poor signal coverage. The most important area where this problem must be solved is inside of buildings, since this is where people spend most of their time. Unfortunately, the in-building enviroment is also the ost challenging area to provide radio coverage due to severe attenuation and multi-path effects. The problem must be tackled from the viewpoint of optimization of performance/cost ratio of the network. In this paper, we describe a system-level approach to tackle this problem. We demonstrate how one can trade-off hardware performance, which represent cost, with proper choice of system architecture which includes, among other factors, in-buiding radio environment, to arrive at an optimum network solution technically and economically.
Dynamics of Wide Bandwidth Semiconductor Lasers
Authors: Tauber Daniel , Bowers John E.
Published: October 2003

In this paper we summarize the most important recent advances and results in high speed diode lasers. These advances have primarily come about as a result of physical understanding of the properties that affect the dynamic performance of these lasers. A great deal of progress has been made in understanding the active region properties of such devices, including the electron and hole transport dynamics as well as the effect of active region doping and strain. At the very high frequencies characteristic of the highest speed lasers reported to date the microwave signal propagation becomes an important issue that can limit the laser bandwidth. The distribution of signals along the laser length due to these effects are discussed, analyzed, and measured, and conclusions about bandwidth and device operation are drawn from the analysis. All of these different issues are summarized in this paper from both a theoretical and experimental perspective. The laser structures that address and overcome the problems caused by such factors are presented along with the best results obtained to date.
High-Speed Direct Modulation of Semiconductor Lasers
Authors: Spencer Robert M. , Greenberg Joseph , Eastman Lester F. , Tsai Chin-Yi , O'Keefe Sean S.
Published: October 2003

The high speed direct modulation of semiconductor lasers has made tremendous progress since the early works of Suemune et al. that proposed for the first time the potential for semiconductor lasers to be directly modulated to frequencies approaching 60–90 GHz. Technical achievements as well as an improved understanding of the role of carrier dynamics in the modulation response have made much of these advances possible. This paper discusses the various methods that have been used to improve the direct modulation bandwidth over the last decade. An Understanding of the theoretical and technical concepts that have led to the development of millimeter-wave directly modulated lasers is critical in understanding how these lasers can be further optimized for efficient operation in a number of optical communication links.
1.55 μm High Speed Partly Gain-Coupled DFB Lasers with Periodically Etched Strained-Layer Quantum Wells
Authors: Makino Toshihiko
Published: October 2003

The high speed performance of partly gain-coupled (GC) DFB lasers consisting of periodically etched strained-layer quantum wells (QW's) is reviewed with comparisons to the equivalent index-coupled (IC) DFB lasers with the same active layers. It is shown that the GC DFB laser has a –3 dB modulation bandwidth of 22 GHz at 10 mW with a stable single mode oscillation at the longer side of the Bragg Stop-band due to in-phase gain coupling. A theoretical analysis is also presented based on the local-normal-mode transfer-matrix laser model which takes into account both the longitudinal distribution of laser parameters and carrier transport effects. The mechanism for high modulation bandwidth of the GC DFB laser is attributed to a higher differential gain due to a reduced carrier transport time which is provided by an effecient carrier injection from the longitudinal etched interface of the QW's.
Sub-Picosecond Mode-Locked Laser Diodes
Authors: Stelmakh N.
Published: October 2003

Recent experiments have shown that laser diodes are capable generating nulses as short as 160 fs, thus approaching the performance of more conventional femtosecond lasers such as Tilsapphire lasers or dye lasers. Regular progress is also accomplished in terms of power and energy efficiency or spectral and spatial brightness with the development of novel semiconductor laser structures. In this paper, we review decisive improvements which have placed laser diodes in category of sub-picosecond lasers. A number of experimental results are used to illustrate the specific characteristics of short-pulse laser diodes as compared to other laser systems. The effects of dispersion and phase modulation are discussed on a basis of theoretical model of chirp mode locking.
High Quality InP Epitaxial Growth Using Flow Rate Modulation Metalorganic Chemical Vapor Deposition
Authors: Lee M. K. , Hu C. C.
Published: October 2003

The characteristics of modified flow rate modulation metalorganic chemical deposition is studied. From observation with the atomic force microscope, the flatness of a InP homoepitaxial layer is improved to atomic scale by phosphine modulation metalorganic chemical vapor deposition. The full width at half maximum 5.6 meV of photoluminescence at 77 K can be achieved under optimum growth conditions. The satellite peak around the near band emission can also be reduced to a negligible quantity under optimum growth conditions. Also, MFME can improve the electrical characteristics of the epilayer with higher electron mobility and lower compensation ratio.
Electroabsorption of Unstrained InGaAs/InAlGaAs Multiple Quantum Well Structure Grown on GaAs Substrates
Authors: Lee Ching-Ting , Nee Tzer-En
Published: October 2003

Large electroabsorption was observed in InGaAs/InAlGaAs multiple quantum well structures grown on GaAs substrates operating near 1.3 μm. The molecular beam epitaxy (MBE) growth of these structures was incorporation of a carefully designed InAlAs multistage strain-relaxed buffer. The optical absorption spectra as a function of the reverse bias at room temperature are shown. The good characteristics of the optical modulators fabricated on this structure have indicated its potential for practical applications of high-speed modulation.
Passive Mode-Locking Techniques of Lasers
Authors: Yang C. C. , Huang Ding-Wei , Hsu Chih-Wei , Liang Sheng-Yau , Lay Choong-Wen , Lin Ming-Shan
Published: October 2003

In the frequency domain, mode-locking of a laser is to "lock" the relative phase of various iongitudinal modes in order to form pulses. In many applications, passive mode-locking is superior to active mode-locking because the former does not need any external active sources as required for the latter. For passive mode-locking, we only need certain nonlinear effects to produce pulse compression mechanisms in laser systems. When the compression mechanism is balanced with some broadening effects, such as group-velocity dispersion, stable pulses can be obtained. In this paper, we first review several passive mode-locking techniques by explaining the pulse compression mechanisms. These techniques include saturable absorption mode-locking, colliding-pulse mode-locking, additive-pulse mode-locking, Kerr-lens mode-locking, nonlinear polarization mode-locking and nonlinear coupling mode-locking. Then, we review some of our research results related to nonlinear polarization mode-locking, nonlinear coupling mode-locking and additive-pulse mode-locking. These results come from the experimental, theoretical and numerical studies of fiber and semiconductor lasers.
Nickel-Indiffusion Waveguide for TE-TM Mode Splitter in Lithium Niobate
Authors: Wang Way-Seen , Liao Yu-Pin , Yang Chih-Hua
Published: October 2003

Optical waveguides fabricated by nickel indiffusion on lithium niobate are reviewed. In particular, the fabrication process, index change versus concentration, wavelength dispersion, process-dependent polarization, propagation loss, and electro-optic modulation of the nickel indiffusion waveguide are discussed. To improve the confinement of single-ordinary polarization waveguide fabricated by nickel indiffusion, a novel waveguide made by zinc and nickel indiffusion is presented for the first time. Though the measured propagation loss of the waveguide is larger, the measured output power contours are found more symmetric. Moreover, several TE-TM mode splitters using one or more nickel indiffusion waveguides for the complete mode sorting effect are discussed.
Numerical Analysis of Nonlinear Directional Couplers
Authors: Lai Chih-Hsien , Chang Hung-Chun , Pang Jia-Pang
Published: October 2003

The original coupled-mode theory for the nonlinear directional coupler (NLDC) and two later improved theories are reviewed and compared with the analysis using the segmentation method proposed in this work. The segmentation method is more accurate in analyzing the NLDC because it takes into account the real situation that the local nonlinear guided modes in the NLDC will vary along the propagation direction due to the accompanying variation in the local power distribution. In the coupled-mode formulations reviewed, however, either linear guided modes or nonlinear modes at a fixed power level are employed when evaluating related coupling quantities.
Quantum-Mechanical Calculations of Resonant Semiconductor Devices: A QMWI Approach
Authors: Tung Hsin-Han , Lee Chien-Ping
Published: October 2003

In this paper we describe two novel resonant semiconductor superlattice structures to serve as quantum-mechanical energy band-pass filters. Such structures allow the incident electrons to be nearly totally transmitted when the impinging electron energy is in the passband. On the other hand, a complete reflection occurs when the impinging energy is in the stopband. This special characteristic can be explained using the concept of quantum-mechanical wave impedance (QMWI) matching method. We also study the scattering effects on the transmission spectrum of a resonant tunneling diode (RTD). The resonant time τwell calculated form QMWI method is compared with the scattering time τs to determine whether the tunneling mechanism is coherent or sequential tunneling.
Electro-Optic Characterization of Microwave Standing Waves in a GaAs Transmission Line by Using a Novel Phase Analyzing Technique
Authors: Pan Ci-Ling , Lin Gong-Ru , Shieh Jia-Min , Tsai Chia-Wen , Wang S.-C. , Wu Hsiao-Hua
Published: October 2003

We demonstrate an accurate, non-contact and compact characterization technique for measuring both the amplitude and phase component of microwave standing-wave patterns in a GaAs microstrip transmission line. A laser-diode-based optoelectronic phase lock loop was employed as a phase-referencing scheme. Key parameters such as voltage standing-wave ratio and reflection coefficient for a GaAs microstrip transmission line were determined up to 16 GHz. Dispersion charateristics were found in good agreement with selected theoretical models.
A Holographic Memory for Digital Data Storage
Authors: Yang C. P. , Lin S. H. , Hsieh M. L. , Hsu K. Y. , Hsieh T. C.
Published: October 2003

A read-only holographic memory for digital data storage is experimentally demonstrated. Techniques for coding and decoding of optical signals, and the interface techniques between the optical memory and a personal computer are described. The performance of the optical memory and the techniques for improving the bit error rate (BER) are presented.
Fixed Point Stability Analysis of Chua's Circuit: A Case Study with a Real Circuit
Authors: Aguirre Luis A. , Tôrres Leonardo A. B.
Published: October 2003

This short paper discusses the effect of the internal resistance of the inductor in Chua's circuit which is often neglected by many even when actual implementation is intended. Using a fixed point stability analysis it is shown that varying the inductor resistance it is possible to suppress or allow chaotic oscillations. The results reported in this paper have clear consequences for the control of Chua's circuit.
A Data Structure on Interval Graphs and Its Applications
Authors: Pal Madhumangal , Bhattacharjee G. P.
Published: October 2003

In this papar, a new data structure, interval tree (IT), is introduced for an interval graph. Some important properties of IT are studies from the algorithmic point of view. It has many advantages compared to the data structures which are commonly used to solve the problems on interval graphs. Using the properties of IT, the following problems are solved on interval graphs:

(i) shortest distances between any two vertices, and (ii) the diameter of the graph.
Chaos in Conditionally Reset Linear Systems
Authors: Aissi Cherif , Fadul Faisal
Published: October 2003

This paper presents a novel and simple design of conditionally reset linear systems which exhibit chaotic behevior. The proposed systems are constructed from building blocks e.g. reset integrator, nonlinear controller, summer and gain amplifiers) which can be either designed or found in the off-shelf electronics library. Throughout the paper, computer simulation results are used to show the stretching and folding mechanism for chaos generation in these systems.
Time-Variant Moving Objects Extraction using Velocity-Tuned Filter Banks and Time-Recursion Method in Infrared Image Sequences
Authors: Choi Jae-Ho , Kim Bong-Tae , Kim Won-Koo
Published: October 2003

A motion vector selective moving object estimation algorithm that preserves the exact shapes and textures of moving objects is presented. In order to extract multiple moving objects with arbitrary motion vectors embedded in the sequence of image frames of cluttered stationary background as alleviating the aliasing effects, both 3D spectral filter banks, called velocity-tuned filter banks, and time-recursive Kalman filter are incorporated to work in parallel. Furthermore, using the fact that the motion energy for each one of the moving objects takes a unique part of the spectrum in the 3D spatio-temporal frequency space, the rotation invariant multiple moving objects detection is also possible when using the proposed filter banks. Simulations have been run to analyze the performance of our filtering algorithm utilizing image sequences of natural scenes. The accurate and robust sets of estimation results are observed down to signal-to-noise ratios of 12 dB.
MCBP Neural Networks for Efficient Recognition of Tire Classification Code
Authors: Koo Gunseo , Lee Gisung , Oh Haeseok
Published: October 2003

In this paper, we have studied a construct code recognition system using a neural network according to an image process taking the DOT classification code stamped on a tire surface. It happened that sometimes characters of the code were distorted at the edge by diffused reflection and two adjacent characters take the same label, being very sensitive to illumination used for recognizing them on the tire. Thus, this paper would propose the algorithm for tire code being conscious of these properties and prove the efficiency of the algorithm with a simulation. Also, we have suggested a MCBP network composing of multi-linked recognizers for the efficient identification of the DOT code as the tire classification code. The MCBP network extracts the projection value for classifying each character's region after taking out its projection on the X and Y axes, processes each character by taking a 7 × 8 normalization. We have improved the accuracy by 3% through the MCBP network and post-process comparing the DOT code database. This approach finally results in the improvement of the learning time to 60% and the recognition rate goes up to 95% from 90%, better than with Back Propagation with post-processing. It has also attained greater rates of tire recognition at 98%.
Extracting Frequency of an Autonomous System by Harmonic Balance
Authors: Peršič Boštjan , Medič Igor
Published: October 2003

Some considerations on initial partitioning of the circuit within harmonic balance analysis are presented. Instead of linear and nonlinear, it is divided into resistive and reactive parts. Following the procedure presented, frequency as a parameter appears no more than once inside each equation, and most of the unknowns are expressed explicitly. The former is advantageous when examining an autonomous system, and the latter enables a simple numerical process. The method proposed is illustrated by an example.
An Adaptive Motion Estimation Based on the Temporal Subband Analysis
Authors: Yim Zung Kon , Chung Jae Ho
Published: October 2003

Motion Estimation is one of the key components in video coding like MPEG. In this paper, a new motion estimation scheme for a MPEG-like video coder is suggested. The proposed "adaptive motion estimation" scheme consists of five function blocks: temporal subband analysis (TSBA), extraction of temporal activity distribution (TAD), scene change detection (SCD), picture type replacement (PTR), and temporally adapted block matching algorithm (TABMA). All five function blocks are developed primarily based on the temporal subband analysis. Our new block matching algorithm TABMA is capable of controlling the size of block matching area searched. According to the significance of TAD, TABMA adjusts its nonuniform motion vector searching area. TABMA guarantees accurate and cost-effective performance. Also, newly proposed SCD and PTR together can prevent poor motion prediction for a video sequence containing abruptly changed scenes in it. As a result of that, SCD and PTR contribute to the reduction of overall computational loads, yet maintaining excellent coding quality.
Automatic Real-Time Identification of Fingerprint Images Using Wavelets and Gradient of Gaussian
Authors: Lee Woo Kyu , Chung Jae Ho
Published: October 2003

In this paper, a fingerprint recognition algorithm is suggested. The algorithm is developed based on the wavelet transform, and the dominant local orientation which is derived from the coherence and the gradient of Gaussian. By using the wavelet transform, the algorithm does not require conventional preprocessing procedures such as smoothing, binarization, thining and restoration. Computer simulation results show that when the rate of Type II error — Incorrect recognition of two different fingerprints as identical fingerprints — is held at 0.0%, the rate of Type I error — Incorrect recognition of two identical fingerprints as different ones — turns out as 2.5% in real time.
Performance of a Simple Highly-Linear MOS Analog Mixer
Authors: Mak Kin Chung , Luong Howard Cam
Published: October 2003

A low-voltage MOS analog mixer using a cross-coupled pair as the core is described. The mixing operation is based on the square-law characteristic of MOS transistor operating in the saturation region. Theory, simulation and measurement show that the mixing characteristic is superior and not sensitive to device mismatches. The realized mixer achieved a DC nonlinearity of less than 0.7% experimentally within an input range of 0.6 Vp-p. The measured IM3 and IMFDR3 are 22.5 dBm and -46.7 dB respectively. It consumes 2 mW power from a single 3.3 V power supply. The active die area is 200 μm × 150 μm.
A New Technique for the High-Level Synthesis of Digit-Serial Digital Filters Based on Genetic Algorithms
Authors: Satyanarayana J. H. , Nowrouzian B.
Published: October 2003

This paper is concerned with the exploitation of genetic algorithms and their application to the development of a new optimization technique for the high-level synthesis of digit-serial digital filter data-paths. In the resulting optimization technique, the cost associated with the final digital filter data-path is minimized subject to user-specified constraints on the number of physical arithmetic functional units employed. The proposed technique is capable of obtaining global area-optimal, time-optimal, or combined area-cum-time-optimal data-paths, where the optimality takes into account not only the cost associated with the required arithmetic functional units but also that associated with the required support cells (multiplexors and registers). This optimization is made computationally effective by encoding the digital filter data flow-graph into chromosomes which preserve the data-dependency relationships in the original digital filter signal flow-graph under the operations of crossover and mutation by the underlying genetic algorithm. The usefulness of the proposed technique is demonstrated by applying to the constrained optimization of a benchmark elliptic wave digital filter for full bit-serial, full bit-parallel, as well as general digit-serial high-level synthesis. The results thus obtained are compared to those of the existing techniques (whenever appropriate) to confirm the validity of the technique.
A Set of Split-Matrix Ordered Walsh Functions
Authors: Wan K. F. , Ching P. C. , Li C. K.
Published: October 2003

A new set of Walsh functions is defined in terms of the split-matrix ordering. The intrinsic properties of the functions are analyzed. The relationship and the associated conversion rules between the newly defined functions and other typical Walsh functions are discussed. It is shown that the proposed Walsh functions provide a straighforward and efficient algorithm for fast Discrete Walsh Transformation.
Port Interchange in Voltage Mode Current Conveyor Based Filters
Authors: Soliman Ahmed M.
Published: October 2003

A transformation method which leads to the generation of high input impedance current conveyor based filters from finite input impedance circuits is given. Applications of the transformation method are included. PSpice simulations and experimental results indicating the performance of the transformed current conveyor circuit compared with the original circuit are also given.
Tellegen's Theorem for Subnetworks
Authors: Cel J.
Published: October 2003

Let [Formula: see text] be a directed network and ℳ its subnetwork. It is proved that [Formula: see text] for all vectors of branch voltages uℳ and currents i ℳ in ℳ satisfying Kirchhoff's voltage and current laws in every loop and cutset of [Formula: see text] contained in ℳ if and only if ℳ is a union of blocks of [Formula: see text]. This yields a version of Tellegen's famous theorem for subnetworks.
Hyperchaotic Coupled Chua Circuits: An Approach for Generating New n×m-Scroll Attractors
Authors: Cafagna Donato , Grassi Giuseppe
Published: October 2003

In this paper an approach for generating new hyperchaotic attractors from coupled Chua circuits is proposed. The technique, which exploits sine functions as nonlinearities, enables n×m-scroll attractors to be generated. In particular, it is shown that n×m-scroll dynamics can be easily designed by modifying four parameters related to the circuit nonlinearities. Simulation results are reported to illustrate the capability of the proposed approach.
Complex Dynamical Behaviors of the Chaotic Chen's System
Authors: Zhou Tianshou , Tang Yun , Chen Guanrong
Published: October 2003

In this paper, the complex dynamical behaviors of the chaotic trajectories of Chen's system are analyzed in detail, with its precise bound derived for the first time. In particular, it is rigorously proved that all nontrivial trajectories of the system always travel alternatively through two specific Poincaré projections for infinitely many times. The results provide an insightful understanding of the complex topological structure of Chen's chaotic attractor.
Bifurcation Analysis of Frequency Locking in a Semiconductor Laser with Phase-Conjugate Feedback
Authors: Green Kirk , Krauskopf Bernd
Published: October 2003

We present a detailed study of the external-cavity modes (ECMs) of a semiconductor laser with phase-conjugate feedback. Mathematically, lasers with feedback are modeled by delay differential equations (DDEs) with an infinite-dimensional phase space. We employ new numerical bifurcation tools for DDEs to continue steady states and periodic orbits, irrespective of their stability. In this way, we show that the periodic orbits corresponding to the ECMs are connected to the steady state solution associated with the locking range of the laser. We also identify symmetric and nonsymmetric homoclinic orbits and hysteresis in the system.
Capture Zones of the Family of Functions λzmexp(z)
Authors: Fagella Núria , Garijo Antonio
Published: October 2003

We consider the family of entire transcendental maps given by Fλ,m(z)=λzm exp (z) where m≥2. All functions Fλ,m have a superattracting fixed point at z=0, and a critical point at z = -m. In the dynamical plane we study the topology of the basin of attraction of z=0. In the parameter plane we focus on the capture behavior, i.e. λ values such that the critical point belongs to the basin of attraction of z=0. In particular, we find a capture zone for which this basin has a unique connected component, whose boundary is then nonlocally connected. However, there are parameter values for which the boundary of the immediate basin of z=0 is a quasicircle.
A Neurobiological Theory of Meaning in Perception Part I: Information and Meaning in Nonconvergent and Nonlocal Brain Dynamics
Authors: Freeman Walter J.
Published: October 2003

The aim of this tutorial is to document a novel approach to brain function, in which the key to understanding is the capacity of brains for self-organization. The property that distinguishes animals from plants is the capacity for directed movement through the environment, which requires an organ capable of organizing information about the environment and predicting the consequences of self-initiated actions. The operations of predicting, planning acting, detecting, and learning comprise the process of intentionality by which brains construct meaning. The currency of brains is primarily meaning and only secondarily information. The information processing metaphor has dominated neurocognitive research for half a century. Brains certainly process information for input and output. They pre-process sensory stimuli before constructing meaning, and they post-process cognitive read-out to control appropriate action and express meaning. Neurobiologists have thoroughly documented sensory information processing bottom-up, and neuropsychologists have analyzed the later stages of cognition top-down, as they are expressed in behavior. However, a grasp of the intervening process of perception, in which meaning forms, requires detailed analysis and modeling of neural activity that is observed in brains during meaningful behavior of humans and other animals. Unlike computers, brains function hierarchically. Sensory and motor information is inferred from pulses of microscopic axons. Meaning is inferred from local mean fields of dendrites in mesoscopic and macroscopic populations. This tutorial is aimed to introduce engineers to an experimental basis for a theory of meaning, in terms of the nonlinear dynamics of the mass actions of large neural populations that construct meaning. The focus is on the higher frequency ranges of cortical oscillations. Part I introduces background on information, meaning and oscillatory activity (EEG). Part II details the properties of wave packets. Part III describes the covariance structure of the oscillations. Part IV addresses the amplitude modulations, and Part V deals with the phase modulations. The significance of a theory of meaning lies in applications using population neurodynamics, to open new approaches for treatment of clinical brain disorders, and to devise new machines with capacities for autonomy and intelligence that might approach those of simpler free-living animals.
Topology of Windows in the High-Dimensional Parameter Space of Chaotic Maps
Authors: Baptista Murilo S. , Grebogi Celso , Barreto Ernest
Published: October 2003

Periodicity is ubiquitous in nature. In this work, we analyze the dynamical reasons for which periodic windows, that appear in parameter space diagrams, have different shapes and structures. For that, we make use of a dynamical quantity, called spine — the skeleton of the window, in order to explain a conjecture that describes the presence of periodic windows in the parameter space of high-dimensional chaotic systems.
A New Approach to Breaking Down Chaotic Secure Communication
Authors: Tao Chao , Du Gonghuan
Published: October 2003

In this paper, we propose the time-varying stable fixed point concept to advance the generalized synchronization and present a general approach to calculating the value of chaotic system parameters according to some signal data. It provides a new approach to studying an unknown chaotic attractor and unmask the chaotic communication. We break down two chaotic communication schemes as examples with this approach.
Periodic Forcing and Goal Oriented Control of Chaos
Authors: Sanju  , Varma V. S.
Published: October 2003

We study control of chaos by periodic modulation without feedback in discrete maps. We show that period-p forcing shifts and splits the naturally occurring period-p windows (and their multiples) and leads to the stabilization of chaos, and that for multiplicative sinusoidal perturbations of the logistic map stabilization can be done at a desired value of the control parameter and at a desired periodicity, simply by varying the amplitude of forcing, provided the modulated system remains bounded.
Maintenance of Geometric Representations Through Space Decompositions
Authors: Shapiro Vadim
Published: October 2003

The ability to transform between distinct geometric representations is the key to success of multiple-representation modeling systems. But the existing theory of geometric modeling does not directly address or support construction, conversion, and comparison of geometric representations. A study of classical problems of CSG ↔ b-rep conversions, CSG optimization, and other representation conversions suggests a natural relationship between a representation scheme and an appropriate decomposition of space. We show that a hierarchy of space decompositions corresponding to different representation schemes can be used to enhance the theory and to develop a systematic approach to maintenance of geometric representations.
Optimal Shortest Path and Minimum-Link Path Queries between Two Convex Polygons inside a Simple Polygonal Obstacle
Authors: Chiang Yi-Jen , Tamassia Roberto
Published: October 2003

We present efficient algorithms for shortest-path and minimum-link-path queries between two convex polygons inside a simple polygon P, which acts as an obstacle to be avoided. Let n be the number of vertices of P, and h the total number of vertices of the query polygons. We show that shortest-path queries can be performed optimally in time O( log h + log n) (plus O(k) time for reporting the k edges of the path) using a data structure with O(n) space and preprocessing time, and that minimum-link-path queries can be performed in optimal time O( log h + log n) (plus O(k) to report the k links), with O(n3) space and preprocessing time.

We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision [Formula: see text]. The update operations consist of insertions and deletions of edges and vertices. Let n be the current number of vertices in [Formula: see text]. The data structure uses O(n) space, supports updates in O( log 2 n) time, and performs shortest-path and minimum-link-path queries in times O( log h+ log 2n) (plus O(k) to report the k edges of the path) and O( log h + k log 2 n), respectively. Performing shortest-path queries is a variation of the well-studied separation problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries.
Efficient Contact Determination in Dynamic Environments
Authors: Lin Ming , Manocha Dinesh
Published: October 2003

The problem of contact determination among multiple objects is fundamental in computer simulated environments and robotics. Most of the earlier work is restricted to either polyhedral models or static environments. In this paper, we present efficient algorithms for contact determination and inference between geometric models in dynamic environments. The set of models include polyhedra and surfaces described by algebraic sets or piecewise algebraic functions. The algorithms make use of temporal and spatial coherence between successive instances and their running time is a function of the motion between successive instances. The main characteristics of these algorithms are their simplicity and efficiency. They have been implemented; their performance on many applications indicates their potential for real-time simulations.
Computational Geometry Column 30
Authors: O'Rourke Joseph
Published: October 2003

Several results from Combinatorial Geometry3 are detailed.
Efficient Algorithms to Detect Null-Homologous Cycles on 2-Manifolds
Authors: Dey Tamal K.
Published: October 2003

Given a cycle of length k on a triangulated 2-manifold, we determine if it is null-homologous (bounds a surface) in O(n+k) optimal time and space where n is the size of the triangulation. Further, with a preprocessing step of O(n) time we answer the same query for any cycle of length k in O(g+k) time, g the genus of the 2-manifold. This is optimal for k < g.
Sparse Arrangements and the Number of Views of Polyhedral Scenes
Authors: Berg Mark de , Halperin Dan , Overmars Mark , Kreveld Marc van
Published: October 2003

In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this number, we investigate arrangements of curves and of surfaces that have a certain sparseness property. Given a collection of n algebraic surface patches of constant maximum degree in 3-space with the property that any vertical line stabs at most k of them, we show that the maximum combinatorial complexity of the entire arrangement that they induce is Θ(n2 k). We extend this result to collections of hypersurfaces in 4-space and to collections of (d > 1)-simplices in d-space, for any fixed d. We show that this type of arrangements (sparse arrangements) is relevant to the study of the maximum number of topologically different views of a polyhedral terrain. For polyhedral terrains with n edges and vertices, we introduce a lower bound construction inducing Ω(n5 α(n)) distinct views, and we present an almost matching upper bound. We then analyze the case of perspective views, point to the potential role of sparse arrangements in obtaining a sharp bound for this case, and present a lower bound construction inducing Ω(n8α(n)) distinct views. For the number of views of a collection of k convex polyhedra with a total of n faces, we show a bound of O(n4 k2) for views from infinity and O(n6 k3) for perspective views. We also present lower bound constructions for such scenes, with Ω(n4 + n2 k4) distinct views from infinity and Ω(n6 + n3 k6) views when the viewpoint can be anywhere in 3-space.
A More Compact Visibility Representation
Authors: Kant Goos
Published: October 2003

In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an [Formula: see text] grid, thereby improving the previous bound of (2n-5)×(n-1). To this end we build in linear time the 4-block tree of a planar graph, which improves previous time bounds. Moreover, this is the first time that the technique of splitting a graph into its 4-connected components is used successfully in graph drawing
Planar Curve Routing for Tethered-Robot Motion Planning
Authors: Hert Susan , Lumelsky Vladimir
Published: October 2003

The following problem appears in robotics. A number of small, circular robots live in a common planar workspace. Each is attached by a flexible cable of finite length to a point on the boundary of this workspace. Each robot has a target point in the workspace it must reach. When a robot has reached its target, its cable will have been dragged out into the workspace and possibly pushed and bent by other robots. The cables remain taut at all times and may not overlap, but may bend around other robots. When only the target points are specified for the robots, their motion can produce arbitrarily complex cable configurations. The more complex a cable configuration is, the more restrictive it is to the motion of the robots. To keep restrictions on the robots' motions at a minimum, it is necessary to specify, in addition to the target points, a configuration of the cables that is as simple as possible but allows all robots to reach their targets. The problem of finding the simplest cable configuration for a given set of target points is shown to reduce to the problem of finding a minimal set of nonintersecting routes in a Euclidean graph whose nodes are the robots' cable line. That no set of edges can intersect any other set of edges is an unusual characteristic of this graph problem. This consideration leads to interesting geometric analysis used to determine which relative placements of the graph edges represent overlapping cable lines. An algorithm is suggested that uses an exhaustive search method with pruning to find a set of nonintersecting routes in the graph that is minimal according to a chosen criterion. The algorithm has been implemented and tested; examples of its performance are given.
Approximate Euclidean Shortest Paths in 3-Space
Authors: Choi Joonsoo , Sellen Juergen , Yap Chee-Keng
Published: October 2003

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. However, there are several gaps in the original description. Besides giving a complete treatment in the framework of bit complexity, we also improve on his subdivision method. Among the tools needed are root-separation bounds and nontrivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.
Query-Sensitive Ray Shooting
Authors: Mitchell Joseph S. B. , Mount David M. , Suri Subhash
Published: October 2003

Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by wallking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(n log n), where n is the total number of vertices in all the obstacles.
Triangulating Topological Spaces
Authors: Edelsbrunner Herbert , Shah Nimish R.
Published: October 2003

Given a subspace [Formula: see text] and a finite set S⊆ℝd, we introduce the Delaunay complex, [Formula: see text], restricted by [Formula: see text]. Its simplices are spanned by subsets T⊆S for which the common intersection of Voronoi cells meets [Formula: see text] in a non-empty set. By the nerve theorem, [Formula: see text] and [Formula: see text] are homotopy equivalent if all such sets are contractible. This paper proves a sufficient condition for [Formula: see text] and [Formula: see text] be homeomorphic.
Shortest Non-Crossing Rectilinear Paths in Plane Regions
Authors: Takahashi Jun-Ya , Suzuki Hitoshi , Nishizeki Takao
Published: October 2003

Let A be a plane region inside an outer rectangle with r rectangular obstacles, and let k terminal pairs lie on the boundaries of the outer rectangle and one of the obstacles. This paper presents an efficient algorithm which finds "non-crossing" rectilinear paths in the plane region A, each connecting a terminal pair without passing through any obstacles, and whose total length is minimum. Non-crossing paths may share common points or line segments but do not cross each other in the plane. The algorithm takes time O(n log n) where n = k + r.
Covering Orthogonal Polygons with Non-Piercing Rectangles
Authors: Mark Keil J.
Published: October 2003

Given a simply connected orthogonal polygon P, a polynomial time algorithm is presented to cover the polygon with the minimum number of rectangles, under the restriction that if A and B are two overlapping rectangles in the cover then either A - B or B - A is connected. The algorithm runs in O(n log n + nm) time, where n is the number of vertices of P and m is the number of edges in the visibility graph of P that are either horizontal, vertical or form the diagonal of an empty rectangle.
Two Algorithms for the Sum of Diameters Problem and a Related Problem
Authors: Alsuwaiyel Muhammad H.
Published: October 2003

Given a set S of points in the plane, we consider the problem of partitioning S into two subsets such that the sum of their diameters is minimized. We present two algorithms with time complexities O(n log 2 n / log log n) and O(n log n / (1 - ∊)), where ∊, 0 < ∊ < 1, is a real number that is dependent on the density of the point set. In almost all practical instances, the second algorithm runs in optimal O(n log n) time, improving all previous results in the case of nonsparse point sets. These bounds follow immediately from two corresponding algorithms with the same time complexities for the following problem: given a set of points S = {p1, p2, …,pn} in the plane sorted in increasing distance from p1, compute the sequence of diameters d1, d2, …, dn, where di= Diam {p1, …, pi} is the diameter of the first i points, 1 ≤ i ≤ n.
Computational Geometry Column 32
Authors: O'Rourke Joseph
Published: October 2003

The proof of Dey's new k-set bound is illustrated.
Reaching a Point with an Unanchored Robot Arm in a Square
Authors: Kantabutra Vitit
Published: October 2003

This paper considers an unanchored n-link robot arm in a square with side length at least as long as the longest arm link. The main result is a necessary and sufficient condition for a point in the square region to be reachable by a specified end of the arm. The condition takes O(n) time to determine. This result represents a continuation of previous work published by Hopcroft, Joseph, and Whitesides, by Kantabutra and Kosaraju, and by Kantabutra.
Separating Translates in the Plane: Combinatorial Bounds and an Algorithm
Authors: Czyzowicz Jurek , Everett Hazel , Robert Jean-Marc
Published: October 2003

Given a family of pairwise disjoint convex sets S in the plane, a set [Formula: see text] is separated from a subset X ⊆ S if there exists a line l such that [Formula: see text] lies on one side of l and the sets in X lie on the other side. In this paper, we establish two combinatorial bounds related to the separation problem for families of n pairwise disjoint translates of a convex set in the plane: 1) there exists a line which separates one translate from at least [Formula: see text] translates, for some constant [Formula: see text] that depends only on the shape of the translates and 2) there is a function [Formula: see text], defined only by the shape of [Formula: see text], such that there exists a line with orientation Θ or [Formula: see text] which separates one translate from at least [Formula: see text] translates, for any orientation Θ. We also present an O(n log (n + k) + k) time algorithm for finding a translate which can be separated from the maximum number of translates amongst families of n pairwise disjoint translates of convex k-gons in the plane.