bluuebunny/crossref_metadata_2025 huggingface dataset:
BIFURCATIONS OF AN EXACTLY SOLVABLE MODEL OF ROTORDYNAMICS
Authors: KUCHERENKO VALERI V. , GÓMEZ-MANCILLA JULIO C.
Published: May 2003

Diverse cyclic responses for an effective and useful nonlinear rotor-bearing-seal system model are studied. In this work two typical cases of self-excited vibrations in turbomachinery are considered: steamwhirl and oilwhip. The first one is an aerodynamic phenomenon induced by the flow of the working fluid at the disc power stages, this excitation being directly proportional to the turbomachine out/input power. The second excitation, oilwhip, is produced by a rotating motion of the lubricating oil film inside the bearings; its magnitude is proportional to the operating speed of the rotor. The studied rotodynamic system model exhibits several mathematical bifurcations which correspond to actual machine behavior, and the analysis for each autoinduced and forced excitation cases, together with its associated bifurcation, is performed. For the autonomous case, as well for the forced excitation exact periodic solutions are obtained. The resulting exact periodic solutions enable the study of multiparameter bifurcation. Completeness of the derived exact solutions for small amplitudes follows from the Hopf bifurcation theorem, which also gives an explanation for the onset of cycles stemming from the equilibrium rest point of the system. Global stability of the rest point for the present rotordynamic model without excitations is proved. The obtained solutions are of engineering importance and they can be used as a tool within a methodology for the preliminary dynamic design nowadays for high speed, or high-performance turbomachinery, as well as for design parameter sensibility analysis. Moreover, it is interesting to notice that for steamwhirl excitation, the onset of the Hopf bifurcation is also the same as the threshold limit for unbounded amplitude responses; whereas for oilwhip, beyond the onset of the Hopf bifurcation there exist a region of stable response limit cycles. The studied model shows a rich and complex behavior.
ASYMPTOTIC SYNCHRONIZATION IN LATTICES OF COUPLED NONIDENTICAL LORENZ EQUATIONS
Authors: CHIU CHUANG-HSIUNG , LIN WEN-WEI , PENG CHEN-CHANG
Published: May 2003

In this paper we study coupled nonidentical Lorenz equations with three different boundary conditions. Coupling rules and boundary conditions play essential roles in the qualitative analysis of solutions of coupled systems. By using Lyapunov stability theory, a sufficient condition is obtained for the global stability of trivial equilibrium of coupled system with Dirichlet condition. Then we restrict our attention on the dynamics of coupled nonidentical Lorenz equations with Neumann/periodic boundary condition and prove that the asymptotic synchronization occurs provided the coupling strengths are sufficiently large. That is, the difference between any two components of solution is bounded by the quantity O(ε/ max {c1, c2, c3}) as t → ∞, where ε is the maximal deviation of parameters of nonidentical Lorenz equations, and c1, c2 and c3 are the specified coupling strengths.
SLOW MANIFOLDS OF SOME CHAOTIC SYSTEMS WITH APPLICATIONS TO LASER SYSTEMS
Authors: RAMDANI SOFIANE , ROSSETTO BRUNO , CHUA LEON O. , LOZI RENÉ
Published: May 2003

In this work we deal with slow–fast autonomous dynamical systems. We initially define them as being modeled by systems of differential equations having a small parameter multiplying one of their velocity components. In order to analyze their solutions, some being chaotic, we have proposed a mathematical analytic method based on an iterative approach [Rossetto et al., 1998]. Under some conditions, this method allows us to give an analytic equation of the slow manifold. This equation is obtained by considering that the slow manifold is locally defined by a plane orthogonal to the tangent system's left fast eigenvector. In this paper, we give another method to compute the slow manifold equation by using the tangent system's slow eigenvectors.

This method allows us to give a geometrical characterization of the attractor and a global qualitative description of its dynamics.

The method used to compute the equation of the slow manifold has been extended to systems having a real and negative eigenvalue in a large domain of the phase space, as it is the case with the Lorenz system. Indeed, we give the Lorenz slow manifold equation and this allows us to make a qualitative study comparing this model and Chua's model.

Finally, we apply our results to derive the slow manifold equations of a nonlinear optical slow–fast system, namely, the optical parametric oscillator model.
THE TRANSITION FROM SOLITONS TO CHAOS IN THE SOLUTION OF THE LOGISTIC EQUATION
Authors: SOBHY MOHAMED I. , STUART BURMAN A.
Published: May 2003

The discrete logistic map was one of the first equations to be studied for the production of chaos. We shall show that a soliton solution exists for the differential logistic equation when the output is the derivative of the dependent variable rather than the variable itself. Furthermore, when the logistic equation is solved using Euler's forward algorithm a transition from a soliton solution to chaos exists and can be accurately predicted. The results are used directly to design an electronic soliton generator.
TIME-DELAY FEEDBACK CONTROL OF COMPLEX PATHOLOGICAL RHYTHMS IN AN ATRIOVENTRICULAR CONDUCTION MODEL
Authors: BRANDT MICHAEL E. , CHEN GUANRONG
Published: May 2003

We describe the emergence of complex cardiac rhythms in a nonlinear model of the atrioventricular (AV) nodal conduction system, and a method based on linear time-delay feedback (LTDF) control for suppressing them. The LTDF controller is effective at suppressing these rhythms by stabilizing the map to one of a set of unstable fixed points. Additionally, we show that the method is robust to both measurement error and experimental noise.
CONTROLLING OSCILLATION AMPLITUDES VIA FEEDBACK
Authors: BERNS DANIEL W. , MOIOLA JORGE L. , CHEN GUANRONG
Published: May 2003

This paper studies feedback control of limit cycle amplitudes in nonlinear systems. A graphical approach to bifurcation control is first briefly introduced, followed by the derivation of a nonlinear control law. Then, a suitable implementation of the design is developed via an approximation of the time-derivative term in the nonlinear state feedback controller. A classical model is finally simulated for illustration of the proposed control method.
ON THE COMPUTATION OF LYAPUNOV EXPONENTS FOR DISCRETE TIME SERIES: APPLICATIONS TO TWO-DIMENSIONAL SYMPLECTIC AND DISSIPATIVE MAPPINGS
Authors: LEGA ELENA , PENNA GABRIELLA DELLA , FROESCHLÉ CLAUDE , CELLETTI ALESSANDRA
Published: May 2003

Many techniques have been developed for the measure of the largest Lyapunov exponent of experimental short data series. The main idea, underlying the most common algorithms, is to mimic the method of computation proposed by Benettin and Galgani [1979]. The aim of the present paper is to provide an explanation for the reliability of some algorithms developed for short time series. To this end, we consider two-dimensional mappings as model problems and we compare the results obtained using the Benettin and Galgani method to those obtained using some algorithms for the computation of the largest Lyapunov exponent when dealing with short data series. In particular we focus our attention on conservative systems, which are not widely investigated in the literature. We show that using standard techniques the results obtained for discrete series related to area-preserving mappings are often unreliable, while dissipative systems are easier to analyze. In order to overcome the problem arising with conservative systems, we develop an alternative method, which takes advantage of the existing techniques. In particular, all algorithms provide a good approximation of the largest Lyapunov exponent in the strong chaotic symplectic case and in the dissipative one. However, the application of standard algorithms provides results which are not in agreement with the theoretical expectation for weak chaotic motions, and sometimes also for regular orbits. On the contrary, the method that we propose in this paper seems to work well for the weak chaotic case. Because of the speed of computation, we suggest to use all algorithms to cross-check the results.
TESTING FOR NONLINEARITY OF THE CONTRACTION SEGMENTS IN UTERINE ELECTROMYOGRAPHY
Authors: RADHAKRISHNAN N. , WILSON JAMES D. , LOWERY CURTIS , MURPHY PAM , ESWARAN HARI
Published: May 2003

In this report, we test for possible nonlinearity of the contraction segments interspersed in a uterine electromyography (EMG), recorded externally with abdominal electrodes. There have been several reports in which the uterine contractility had been assumed to be an auto-regressive process and others have hypothesized it as a nonlinear process and possibly chaotic. The surrogate data testing was used successfully to detect nonlinear behavior of physiological systems. However, there have been case studies, which discuss spurious identification of nonrandom structures. The proper choice of the null hypothesis and discriminant statistics plays a crucial role in the surrogate data testing. We have chosen the approximate entropy as the discriminant statistic for our tests. The null hypothesis addressed here is that the uterine contraction is a linearly correlated noise transformed by a nonlinear function. We applied the Amplitude Adjusted Fourier Transform (AAFT) and the Iterated Amplitude Adjusted Fourier Transform (IAAFT) tests to the uterine contraction data. The Kolmogorov Smirnov (D) statistics identified the discriminant values of the surrogates to be from a Gaussian distribution. Parametric testing showed a very low significance value, (~2σ), which indicated the absence of nonrandom structure in the contraction segment.
NUMERICAL COMPUTATION OF HOMOCLINIC ORBITS FOR FLOWS
Authors: CHAN WHEI-CHING C. , WANG DAH-ZEN
Published: May 2003

It is shown that numerical computation of homoclinic orbits for flows will generate transverse homoclinic points when one uses very accurate schemes.
THE SPATIAL ENTROPY OF TWO-DIMENSIONAL SUBSHIFTS OF FINITE TYPE
Authors: JUANG JONQ , LIN SONG-SUN , SHIEH SHIH FENG , LIN WEN-WEI
Published: May 2003

In this paper, two recursive formulas for computing the spatial entropy of two-dimensional subshifts of finite type are given. The exact entropy of a nontrivial example arising in cellular neural networks is obtained by using such formulas. We also establish some general theory concerning the spatial entropy of two-dimensional subshifts of finite type. In particular, we show that if either of the transition matrices is rank-one, then the associated exact entropy can be explicitly obtained. The generalization of our results to higher dimension can be similarly obtained. Furthermore, these formulas can be used numerically for estimating the spatial entropy.
NOISE PERFORMANCE OF A SYNCHRONIZATION SCHEME THROUGH COMPOUND CHAOTIC SIGNAL
Authors: LORENZO M. N. , PÉREZ-MUÑUZURI V. , PÉREZ-VILLAR V. , MURALI K.
Published: May 2003

A synchronization scheme through compound chaotic signal is analyzed both numerically and experimentally to study the performance of this scheme, in a noisy environment, considering its possibilities for communication systems with masking technique. The influence of noise has been analyzed in terms of the Bit Error Rate. An important factor of this method is the use of encryption keys which add more robustness and complexity to the system.
POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER
Authors: BREMNER DAVID , SHERMER THOMAS
Published: May 2003

A visibility relation can be viewed as a graph: the uncountable graph of a visibility relationship between points in a polygon P is called the point visibility graph (PVG) of P. In this paper we explore the use of perfect graphs to characterize tractable subproblems of visibility problems. Our main result is a characterization of which polygons are guaranteed to have weakly triangulated PVGs, under a generalized notion of visibility called [Formula: see text]-visibility. Let [Formula: see text] denote a set of line orientations. A connected point set P is called [Formula: see text]-convex if the intersection of P with any line with orientation in [Formula: see text] is connected. Two points in a polygon are said to be [Formula: see text]-visible if there is an [Formula: see text]-convex path between them inside the polygon. Let [Formula: see text] denote the set of orientations perpendicular to orientations in [Formula: see text]. Let [Formula: see text] be the set of orientations θ such that a "reflex" local maximum in the boundary of P exists with respect to θ. Our characterization of which polygons have weakly-triangulated PVGs is based on restricting the cardinality and span of [Formula: see text]. This characterization allows us to exhibit a class of polygons admitting a polynomial algorithm for [Formula: see text]-convex cover.
ALTERNATING HAMILTON CYCLES WITH MINIMUM NUMBER OF CROSSINGS IN THE PLANE
Authors: KANEKO ATSUSHI , KANO M. , YOSHIMOTO KIYOSHI
Published: May 2003

Let X and Y be two disjoint sets of points in the plane such that |X|=|Y| and no three points of X ∪ Y are on the same line. Then we can draw an alternating Hamilton cycle on X∪Y in the plane which passes through alternately points of X and those of Y, whose edges are straight-line segments, and which contains at most |X|-1 crossings. Our proof gives an O(n2 log n) time algorithm for finding such an alternating Hamilton cycle, where n =|X|. Moreover we show that the above upper bound |X|-1 on crossing number is best possible for some configurations.
ORTHOGONAL EDGE VISIBILITY GRAPHS OF POLYGONS WITH HOLES
Authors: SRINIVASARAGHAVAN G. , MUKHOPADHYAY ASISH
Published: May 2003

In this paper we report on a set of six necessary conditions that must be satisfied by the edge visibility graph of an orthogonal polygon with holes. We have also proved the following significant result: If G is a connected, bipartite, planar, and irreducible (in a sense defined in the paper) graph then it can be realized (that is, there is a corresponding orthogonal polygon with holes) up to leaf addition.
COMPUTATIONAL GEOMETRY COLUMN 37
Authors: DEMAINE ERIK D. , O'ROURKE JOSEPH
Published: May 2003

Open problems from the 15th Annual ACM Symposium on Computational Geometry.
EXACT AND OPTIMAL CONVEX HULLS IN 2D
Authors: RATSCHEK HELMUT , ROKNE JON
Published: May 2003

We present an algorithm for computing the convex hull of a finite set of points. The algorithm is based on a version of Graham scan with the following additional features:

• If the points are already (single precision) machine numbers, the computation is rounding-error free, that is, the computed hull is the hull that would have been computed if real arithmetic was available.

• If the points are arbitrary numbers, the algorithm renders the smallest possible machine representable convex hull that includes the exact convex hull.

• The computation time is still O(n log 2n).

• Only floating point arithmetic with double mantissa length is required. No mantissa splitting or other mantissa manipulations are needed; one only has to know the exponent parts of the numbers. Also, no fixed point accumulator is needed.

• Single precision interval arithmetic is recommended for accelerating the computation, but is not necessary.

• All of these aims are achieved with a new method for exact determination of the sign of a sum.
THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS
Authors: BAEK NAKHOON , SHIN SUNG-YONG , CHWA KYUNG-Yong
Published: May 2003

Plane sweep plays an important role in computational geometry. This paper shows that an extension of topological plane sweep to three-dimensional space can calculate the volume swept by rotating a solid polyhedral object about a fixed axis. Analyzing the characteristics of rotational swept volumes, we present an incremental algorithm based on the three-dimensional topological sweep technique. Our solution shows the time bound of O(n2·2α(n)+Tc), where n is the number of vertices in the original object and T c is time for handling face cycles. Here, α(n) is the inverse of Ackermann's function.
An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
Authors: ALEKSANDROV LYUDMIL G. , DJIDJEV HRISTO N. , SACK JÖRG-RÜDIGER
Published: May 2003

A central link segment of a simple n-vertex polygon P is a segment s inside P that minimizes the quantity max x∈P min y∈sdL(x,y), where dL(x,y) is the link distance between points x and y of P. In this paper we present an O (n log n) algorithm for finding a central link segment of P. This generalizes previous results for finding an edge or a segment of P from which P is visible. Moreover, in the same time bound, our algorithm finds a central link segment of minimum length. Constructing a central link segment has applications to the problems of finding an optimal robot placement in a simply connected polygonal region and determining the minimum value k for which a given polygon is k-visible from some segment.
POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
Authors: WISMATH S. K.
Published: May 2003

In general, visibility reconstruction problems involve determining a set of objects in the plane that exhibit a specified set of visibility constraints. In this paper, an algorithm is presented for reconstructing a set of parallel line segments from specified visibility information contained in an extended endpoint visibility graph. The algorithm runs in polynomial time and relies on simple vector arithmetic to generate a system of linear inequalities. A related problem, solvable with the same technique, is the point reconstruction problem, in which the cyclic ordering and the x-coordinates of a set of points is specified.

A second contribution is the definition of an extension of the visibility graph called the Stab Graph, which contains extra visibility information.
SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER
Authors: LEE JAE-HA , PARK SANG-MIN , CHWA KYUNG-YONG
Published: May 2003

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region [Formula: see text] with a specified boundary point d, is it possible for a 1-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within [Formula: see text], before the intruder reaches d? We decide this question in O (n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n2)-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.
COMPUTATIONAL GEOMETRY COLUMN 38
Authors: O'ROURKE JOSEPH
Published: May 2003

Recent results on curve reconstruction are described.
UNSTRUCTURED MESH GENERATION: THEORY, PRACTICE, AND PERSPECTIVES
Authors: TENG SHANG-HUA , WONG CHI WAI
Published: May 2003

Mesh generation is a great example of inter-disciplinary research. Its development is built upon advances in computational and combinatorial geometry, data structures, numerical analysis, and scientific applications. Its success is justified not only by mathematical proofs about the quality and the numerical relevancy of geometry-based meshing algorithms, but also by the performance of meshing software in real applications. It embraces both provably good algorithms and practical heuristics. This paper presents a brief overview of algorithms, theorems, and software in mesh generation.
ADAPTIVE SIMPLICIAL GRIDS FROM CROSS-SECTIONS OF MONOTONE COMPLEXES
Authors: EDELSBRUNNER HERBERT , WAUPOTITSCH ROMAN
Published: May 2003

We study the maintenance of a simplicial grid or complex under changing density requirements. The proposed method works in any fixed dimension and generates grids by projecting cross-sections of a monotone simplicial complex that lives in one dimension higher than the grid. The density of the grid is adapted by locally moving the cross-section up or down along the extra dimension.
HIGH QUALITY QUADRILATERAL SURFACE MESHING WITHOUT TEMPLATE RESTRICTIONS: A NEW APPROACH BASED ON NETWORK FLOW TECHNIQUES
Authors: MÜLLER–HANNEMANN MATTHIAS
Published: May 2003

We investigate a purely combinatorial approach to the following mesh refinement problem: Given a coarse mesh of polygons in three-dimensional space, find a decomposition into well-shaped quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints.

We present a new approach based on network flow techniques. In particular, we show that this problem can efficiently be solved by a reduction to a minimum cost bidirected flow problem, if the mesh does not contain branching edges, that is, edges incident to more than two polygons. This approach handles optimization criteria such as density, angles and regularity. In our model we get rid of restrictions on the set of feasible solutions imposed by templates. On the other hand, we still use advantages of general templates with respect to mesh quality for the individual refinement of the mesh polygons.

For meshes with branchings, the problem is feasible if and only if a certain system of linear equations over GF(2) has a solution. To enhance the mesh quality for meshes with branchings, we introduce a two-stage approach which first decomposes the whole mesh into components without branchings, and then uses minimum cost bidirected flows on the components in a second phase. We report on our computational results which indicate that this approach usually leads to a very high mesh quality.
VIRTUAL TOPOLOGY OPERATORS FOR MESHING
Authors: SHEFFER ALLA , BERCOVIER MICHEL , BLACKER TED , CLEMENTS JAN
Published: May 2003

In recent years several automatic 3D meshing algorithms have emerged. However direct analysis of CAD models is still elusive. Among the major obstacles preventing automation is the necessity to edit the CAD models to be suitable both for the analysis objectives and the available meshing algorithms. Such editing includes topology correction and validation, detail suppression and decomposition. Editing the geometry directly (e.g. surface redefinitions) is cumbersome, tedious, and expensive. Introducing virtual topology allows such operations as modifications to the topology only. In this work the concept and operators of virtual topology are described, along with their use in performing the required editing of the model. A set of automatic and semi-automatic tools for the various editing operations are introduced.
SOLUTION-BASED MESH QUALITY INDICATORS FOR TRIANGULAR AND TETRAHEDRAL MESHES
Authors: BERZINS MARTIN
Published: May 2003

A new mesh quality measure for triangular and tetrahedral meshes is presented. This mesh quality measure is based both on geometrical and solution information and is derived by considering the error when linear triangular and tetrahedral elements are used to approximate a quadratic function. The new measure is shown to be related to existing measures of mesh quality but with the advantage that local solution information in the form of scaled derivatives along edges is taken into account. This advantage is demonstrated by a comparison with a geometrical indicator on a parameterized problem.
OCTREE-BASED HEXAHEDRAL MESH GENERATION
Authors: SCHNEIDERS ROBERT
Published: May 2003

An octree-based algorithm for the generation of hexahedral element meshes is presented. The algorithm works in three steps: (i) The geometry to be meshed is approximated by an octree structure. (ii) An unstructured hexahedral element mesh is derived from the octree. (iii) The mesh is adapted to the boundary of the geometry. We focus on step (ii) and describe an algorithm that constructs a hex mesh for a given octree structure.
HIGH FIDELITY INTERVAL ASSIGNMENT
Authors: MITCHELL SCOTT A.
Published: May 2003

Quadrilateral meshing algorithms impose certain constraints on the number of intervals or mesh edges of the curves bounding a surface. When constructing a conformal mesh of a collection of adjoining surfaces, the constraints for all of the surfaces must be simultaneously satisfied. These constraints can be formulated as an integer linear program. Not all solutions to this problem are equally desirable, however. The user typically indicates a goal (soft-set) or required (hard-set) number of intervals for each curve. The hard-sets constrain the problem further, while the soft-sets influence the objective function.

This paper describes an algorithm for solving this interval assignment problem. In a good solution, for each curve the positive or negative difference between its goal and assigned number of intervals is small relative to its number of goal intervals. The algorithm solves a series of linear programs, and comes close to minimizing the maximum lexicographic vector of these weighted differences. Then the algorithm solves a nearby mixed-integer linear program to satisfy certain "sum-even" constraints. The algorithm reliably produces numbers of intervals that are very close to the user's desires and is easily extendible to new constraints. Earlier versions of the algorithm1 were slower than alternative algorithms, but this is no longer a significant issue; in practice, the running time is a minor fraction of the time to mesh, even in models composed of thousands of curves.
ANISOTROPIC TRIANGULATION OF PARAMETRIC SURFACES VIA CLOSE PACKING OF ELLIPSOIDS
Authors: SHIMADA KENJI , YAMADA ATSUSHI , ITOH TAKAYUKI
Published: May 2003

This paper describes a new computational method of fully automated anisotropic triangulation of a trimmed parametric surface. Given as input: (1) a domain geometry and (2) a 3×3 tensor field that specifies a desired anisotropic node-spacing, this new approach first packs ellipsoids closely in the domain by defining proximity-based interacting forces among the ellipsoids and finding a force-balancing configuration using dynamic simulation. The centers of the ellipsoids are then connected by anisotropic Delaunay triangulation for a complete mesh topology. Since a specified tensor field controls the directions and the lengths of the ellipsoids' principal axes, the method generates a graded anisotropic mesh whose elements conform precisely to the given tensor field.
COMPUTATIONAL GEOMETRY COLUMN 39
Authors: O'ROURKE JOSEPH
Published: May 2003

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
EFFICIENT APPROXIMATION OF CONVEX POLYGONS
Authors: LOPEZ MARIO A. , REISNER SHLOMO
Published: May 2003

We present algorithms for the approximation of a convex n-gon by a convex k-gon (k<n) which inscribes or circumscribes the original polygon. Our algorithms run in O(n+(n-k) log n) time and are easy to implement. Their accuracy, in the sense of area-difference, is analyzed and shown to be of the best order possible for a general algorithm. In particular, this analysis settles a question raised by O'Rourke on the performance of the approximation algorithm of Dori and Ben-Bassat.
EXACT SOLUTIONS OF RECTANGULAR PARTITIONS VIA INTEGER PROGRAMMING
Authors: DE MENESES CLÁUDIO N. , DE SOUZA CID C.
Published: May 2003

Given a rectangle R in the plane and a finite set P of points in its interior, consider the partitions of the surface of R into smaller rectangles. A partition is feasible with respect to P if each point in P lie on the boundary of some rectangle of the partition. The length of a partition is computed as the sum of the lengths of the line segments defining the boundary of its rectangles. The goal is to find a feasible partition with minimum length. This problem, denoted by RGP, belongs to [Formula: see text]-hard and has application in VLSI design. In this paper we investigate how to obtain exact solutions for the RGP. We introduce two different Integer Programming formulations and carry out a theoretical study to evaluate and compare the strength of their bounds. Computational experiments are reported for Branch-and-Cut and Branch-and-Price algorithms we have implemented for the first and the second formulation, respectively. Randomly generated instances with |P|≤200 are solved exactly. The tests indicate that the size of the instances solved with our algorithms decrease by an order of magnitude in the absence of corectilinear points in P, a special case of RGP whose complexity is still open.
OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS
Authors: BESPAMYATNIKH SERGEI , KEDEM KLARA , SEGAL MICHAEL , TAMIR ARIE
Published: May 2003

We present efficient algorithms for two problems of facility location. In both problems we want to determine the location of a single facility with respect to n given sites. In the first we seek a location that maximizes a weighted distance function between the facility and the sites, and in the second we find a location that minimizes the sum (or sum of the squares) of the distances of k of the sites from the facility.
VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME
Authors: KEIL MARK , MOUNT DAVID M. , WISMATH S. K.
Published: May 2003

Given a set S of n non-intersecting line segments in the plane, we vpresent a new technique for efficiently traversing the endpoint visibility graph of S to solve a variety of visibility problems in output sensitive time. In particular, we develop two techniques to compute the 2n visibility polygons of the endpoints of S, in output sensitive time.

Depth-first spiralling is a technique that relies on the ordered endpoint visibility graph information to traverse the endpoints of S in a spiral-like manner using a combination of Jarvis' March and depth-first search. It is a practical method and has been implemented in C++ using LEDA.
THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING
Authors: BIEDL THERESE C. , MADDEN BRENDAN P. , TOLLIS IOANNIS G.
Published: May 2003

In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study orthogonal drawing algorithms that work for any input graph, and discuss different models for such drawings. Then we introduce the three-phase method, a generic technique to create high-degree orthogonal drawings. This approach simplifies the description and implementation of orthogonal graph drawing, and can be applied to global as well as interactive and incremental settings.
OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM
Authors: BEN-MOSHE BOAZ , KATZ MATTHEW J. , SEGAL MICHAEL
Published: May 2003

We present efficient algorithms for several instances of the following facility location problem. Place k obnoxious facilities, with respect to n given demand sites and m given regions, where the goal is to maximize the minimal distance between a demand site and a facility, under the constraint that each of the regions must contain at least one facility.

We also present an efficient solution to the following planar problem that arises as a subproblem. Given n transmitters, each of range r, construct a compact data structure that supports coverage queries, i.e., determine whether a query polygonal/rectangular region is fully covered by the transmitters.
QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS
Authors: MOUNT DAVID M. , NETANYAHU NATHAN S. , PIATKO CHRISTINE D. , SILVERMAN RUTH , WU ANGELA Y.
Published: May 2003

Given a set P of n points in Rd, a fundamental problem in computational geometry is concerned with finding the smallest shape of some type that encloses all the points of P. Well-known instances of this problem include finding the smallest enclosing box, minimum volume ball, and minimum volume annulus. In this paper we consider the following variant: Given a set of n points in Rd, find the smallest shape in question that contains at least k points or a certain quantile of the data. This type of problem is known as a k-enclosing problem. We present a simple algorithmic framework for computing quantile approximations for the minimum strip, ellipsoid, and annulus containing a given quantile of the points. The algorithms run in O(n log n) time.
EQUIVALENCE OF TOPOLOGICAL FORM FOR CURVILINEAR GEOMETRIC OBJECTS
Authors: ANDERSSON L.-E. , PETERS T. J. , STEWART N. F.
Published: May 2003

Given a curvilinear geometric object in R3, made up of properly-joined parametric patches defined in terms of control points, it is of interest to know under what conditions the object will retain its original topological form when the control points are perturbed. For example, the patches might be triangular Bézier surface patches, and the geometric object may represent the boundary of a solid in a solid-modeling application. In this paper we give sufficient conditions guaranteeing that topological form is preserved by an ambient isotopy. The main conditions to be satisfied are that the original object should be continuously perturbed in a way that introduces no self-intersections of any patch, and such that the patches remain properly joined. The patches need only have C0 continuity along the boundaries joining adjacent patches. The results apply directly to most surface modeling schemes, and they are of interest in several areas of application.
DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY
Authors: DI BATTISTA GIUSEPPE , GARG ASHIM , LIOTTA GIUSEPPE , PARISE ARMANDO , TAMASSIA ROBERTO , TASSINARI EMANUELE , VARGIU FRANCESCO , VISMARA LUCA
Published: May 2003

In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice.
COMPUTATIONAL GEOMETRY COLUMN 40
Authors: O'ROURKE JOSEPH
Published: May 2003

It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.
VIRTUAL GEOEXPLORATION: CONCEPTS AND DESIGN CHOICES
Authors: PAJAROLA RENATO , WIDMAYER PETER
Published: May 2003

A trip through a virtual world is a powerful metaphor and a natural way of interacting with a geographic information system (GIS). Virtual reality (VR) systems provide visual realism and real-time navigation and interaction for data in core, but fail to cope with very large amounts of data, and to provide the general functionality of information systems. We describe a prototype system that overcomes these problems by coupling two platforms: A client that runs the VR component interacts via a (local or wide area) network with a server that runs an object oriented database containing geographic data. For the purpose of accessing data efficiently, we describe how to integrate a geometric index into the database, and how to perform the operations that are requested in a real-time trip through the virtual world.
A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
Authors: TAMASSIA ROBERTO , VISMARA LUCA
Published: May 2003

The goal of this paper is to prove the applicability of algorithm engineering and software design concepts to geometric computing through a vertical case study on the implementation of planar point location algorithms. The work is presented within the framework of the GEOMLIB project, aimed at developing an easy to use, reliable, and flexible library of robust and efficient geometric algorithms. We present the criteria that have inspired the preliminary design of GEOMLIB and discuss the guidelines that we have followed in the initial implementation.
TOWARDS WEB-BASED COMPUTING
Authors: AOKI KIYOKO F. , LEE D. T.
Published: May 2003

In a problem solving environment for geometric computing, a graphical user interface, or GUI, for visualization has become an essential component for geometric software development. In this paper we describe a visualization system, called GeoJAVA, which consists of a GUI and a geometric visualization library that enables the user or algorithm designer to (1) execute and visualize an existing algorithm in the library or (2) develop new code over the Internet. The library consists of geometric code written in C/C++. The GUI is written using the Java programming language. Taking advantage of the socket classes and system-independent application programming interfaces (API's) provided with the Java language, GeoJAVA offers a platform independent environment for distributed geometric computing that combines Java and C/C++. Users may remotely join a "channel" or discussion group in a location transparent manner to do collaborative research. The visualization of an algorithm, a C/C++ program located locally or remotely and controlled by a "floor manager", can be viewed by all the members in the channel through a visualization sheet called GeoJAVASheet. A chat box is also provided to enable dialogue among the members. Furthermore, this system not only allows visualization of pre-compiled geometric code, but also serves as a web-based programming environment where the user may submit a geometric code, compile it with the libraries provided by the system, and visualize it directly over the web sharing it with other users immediately.
BOOLE: A BOUNDARY EVALUATION SYSTEM FOR BOOLEAN COMBINATIONS OF SCULPTURED SOLIDS
Authors: KRISHNAN S. , MANOCHA D. , GOPI M. , CULVER T. , KEYSER J.
Published: May 2003

In this paper we describe a system, BOOLE, that generates the boundary representations (B-reps) of solids given as a CSG expression in the form of trimmed Bézier patches. The system makes use of techniques from computational geometry, numerical linear algebra and symbolic computation to generate the B-reps. Given two solids, the system first computes the intersection curve between the two solids using our surface intersection algorithm. Using the topological information of each solid, it computes various components within each solid generated by the intersection curve and their connectivity. The component classification step is performed by ray-shooting. Depending on the Boolean operation performed, appropriate components are put together to obtain the final solid. We also present techniques to parallelize this system on shared memory multiprocessor machines. The system has been successfully used to generate B-reps for a number of large industrial models including parts of a notional submarine storage and handling room (courtesy - Electric Boat Inc.) and Bradley fighting vehicle (courtesy - Army Research Labs). Each of these models is composed of over 8000 Boolean operations and is represented using over 50,000 trimmed Bézier patches. Our exact representation of the intersection curve and use of stable numerical algorithms facilitate an accurate boundary evaluation at every Boolean set operation and generation of topologically consistent solids.
EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION
Authors: ASANO TETSUO , CHEN DANNY Z. , KATOH NAOKI , TOKUYAMA TAKESHI
Published: May 2003

Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation problem, assuming that the sought object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in a grid of N×N pixels is NP-hard under the interclass variance, a criterion that is often used in discriminant analysis. More importantly, we consider the basic case in which the object is bounded by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing the optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(N4) time; this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown planar point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an ∊-approximate solution in O(∊-1 N2 log L) time, where ∊ is any fixed constant with 1>∊>0, and L is the total sum of the absolute values of the brightness levels of the image.
LABELING A RECTILINEAR MAP WITH SLIDING LABELS
Authors: KIM SUNG KWON , SHIN CHAN-SU , YANG TAE-CHEON
Published: May 2003

A rectilinear map consists of a set of mutually non-intersecting rectilinear (i.e., horizontal or vertical) line segments, and each segment is allowed to use a rectangular label of height B and length the same as the segment. Sliding labels are not restricted to any finite number of predefined positions but can slide and be placed at any position as long as it intersects the segment. This paper considers three versions of the problem of labeling a rectilinear map with sliding labels and presents efficient exact and approximation algorithms for them.
LABELING POINTS WITH CIRCLES
Authors: STRIJK TYCHO , WOLFF ALEXANDER
Published: May 2003

We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(n log n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.
REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY
Authors: CHEONG OTFRIED , OOSTRUM RENÉ VAN
Published: May 2003

Assume a robot that, when directed to move in a particular direction, is guaranteed to move inside a cone of angle α centered at the specified direction. The robot has to reach a convex polygonal goal G, while avoiding polygonal obstacles of complexity n. We show that the complexity of the safe region, from where the robot can reach the goal with a single motion with uncertainty α, is O(m+n), and can be computed in time O((m+n) log (m+n)), if α is assumed constant.
A CONVEX DEFICIENCY TREE ALGORITHM FOR CURVED POLYGONS
Authors: SHAPIRO VADIM
Published: May 2003

Boolean set representations of curved two-dimensional polygons are expressions constructed from planar halfspaces and (possibly regularized) set operations. Such representations arise often in geometric modeling, computer vision, robotics, and computational mechanics. The convex deficiency tree (CDT) algorithm described in this paper constructs such expressions automatically for polygons bounded by linear and curved edges that are subsets of convex curves. The running time of the algorithm is not worse than O(n2 log n) and the size of the constructed expressions is linear in the number of polygon edges. The algorithm has been fully implemented for polygons bounded by linear and circular edges.
COMPUTATIONAL GEOMETRY COLUMN 41
Authors: O'ROURKE JOSEPH
Published: May 2003

The recent result that n congruent balls in ℝd have at most 4 distinct geometric permutations is described.
EXACT GEOMETRIC COMPUTATION USING CASCADING
Authors: BURNIKEL CHRISTOPH , FUNKE STEFAN , SEEL MICHAEL
Published: May 2003

In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develop an easy-to-use expression compiler called EXPCOMP. EXPCOMP supports all common operations [Formula: see text]. Applying a new semi-static filter, EXPCOMP combines the speed of static filters with the power of dynamic filters. The filter stages deal with all kinds of floating-point exceptions, including underflow. The resulting programs show a very good runtime behaviour.
EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE
Authors: ANDRADE MARCUS VINÍCIUS ALVIM , STOLFI JORGE
Published: May 2003

We describe exact representations and algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a circle, computing the intersection of two circles, and ordering three arcs out of the same point. These tools support robust and efficient operations on maps overs the sphere, such as point location and map overlay, and provide a reliable framework for robotics, geographic information systems, and other geometric applications.
ON ENUMERATING AND SELECTING DISTANCES
Authors: CHAN TIMOTHY M.
Published: May 2003

Given an n-point set, the problems of enumerating the k closest pairs and selecting the k-th smallest distance are revisited. For the enumeration problem, we give simpler randomized and deterministic algorithms with O(n log n+k) running time in any fixed-dimensional Euclidean space. For the selection problem, we give a randomized algorithm with running time O(n log n+n2/3k1/3 log 5/3n) in the Euclidean plane. We also describe output-sensitive results for halfspace range counting that are of use in more general distance selection problems. None of our algorithms requires parametric search.
RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
Authors: CRAUSER A. , FERRAGINA P. , MEHLHORN K. , MEYER U. , RAMOS E. A.
Published: May 2003

We show that the well-known random incremental construction of Clarkson and Shor18 can be adapted to provide efficient external-memory algorithms for some geometric problems. In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line segments in the plane with K pairwise intersections, that requires [Formula: see text] expected disk accesses, where M is the size of the available internal memory and B is the size of the block transfer. The approach is sufficiently general to derive algorithms for other geometric problems: 3-d half-space intersections, 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched planar point location; these algorithms require an optimal expected number of disk accesses and are simpler than the ones previously known. The results extend to an external-memory model with multiple disks.