bluuebunny/crossref_metadata_2025 huggingface dataset:
THE IMPACT OF INTELLIGENT TOOLS ON SIMULATION METHODOLOGY
Authors: SAVORY PAUL A. , MACKULAK GERALD T.
Published: September 2004

Simulation is one of the most effective techniques for analyzing stochastic systems. Recent computer software and hardware advances have had an important impact on the traditional discrete-event simulation methodology. Intelligent simulation environments consisting of integrated sets of “intelligent” tools for performing simulation studies have emerged. These tools significantly impact the methodology of a simulation analysis. This paper defines these intelligent tools and discusses how they alter the simulation paradigm by illustrating the development of a simulation model using an intelligent simulation environment. Special emphasis is on how an intelligent simulation environment provides a responsive analysis technique for studying manufacturing systems.
PERTS: A PROTOTYPING ENVIRONMENT FOR REAL-TIME SYSTEMS
Authors: LIU J.W.S. , LIU C.L. , DENG Z. , TIA T.S. , SUN J. , STORCH M. , HULL D. , REDONDO J.L. , BETTATI R. , SILBERMAN A.
Published: September 2004

This paper describes PERTS, a prototyping environment for real-time systems. PERTS provides a comprehensive set of design, validation, and simulation tools that are built on recent theoretical advances. It also provides software modules that implement wellknown and novel real-time scheduling algorithms, task and resource assignment algorithms, and resource access control protocols. Together, the tools and software modules support the systematic and rigorous evaluation of new designs, experimentation with alternative scheduling and resource management strategies, and the evaluation and validation of the resultant real-time system.
A SOFTWARE ENGINEERING DESIGN TOOL FOR MODELING HARD REAL-TIME PERFORMANCE
Authors: FOWLER K.J.
Published: September 2004

Hard real-time digital systems are a small but important segment of the installed software base because of failure impact. Deadline feasibility can be optimally determined in this domain through rate monotonic analysis, but performance is difficult to predict unless design change effects on spare capacity are measured. We measure units of concurrency as formal aggregations of reusable modules. In this manner, object-oriented construction can be compatible with hard real-time response requirements.
DOMAIN-SPECIFIC SOFTWARE ARCHITECTURES FOR GUIDANCE, NAVIGATION AND CONTROL
Authors: BINNS PAM , ENGLEHART MATT , JACKSON MIKE , VESTAL STEVE
Published: September 2004

We describe two languages and associated tools for capturing and analyzing two different views of the architecture of an embedded system. One language is tailored to address guidance, navigation, and feedback control issues, while the other is tailored to address real-time, fault-tolerance, secure partitioning, and scalable multiprocessor issues. Both languages have tools that perform analyses appropriate for the issues each addresses, and tools to automatically configure the application software from a sufficiently detailed specification. The integrated languages and tools are intended to support a development process based on reusing an easily configurable generic architecture developed for a family of products.
SPECIFICATION AND ANALYSIS OF REAL-TIME SYSTEMS USING CSP AND PETRI NETS
Authors: KAVI KRISHNA M. , SHELDON FREDERICK T. , REED SHERMAN
Published: September 2004

Formal methods such as CSP (Communicating Sequential Processes) are widely used for reasoning about concurrency, communication, safety, and liveness issues. Some of these models have been extended to permit reasoning about real-time constraints. Yet, the research in formal specification and verification of complex systems has often ignored the specification of stochastic properties of the system under study. We are developing methods and tools to permit stochastic analyses of CSP-based specifications. Our basic objective is to evaluate candidate design specifications by converting formal systems descriptions into the information needed for analysis. In doing so, we translate a CSP-based specification into a Petri net which is analyzed to predict system behavior in terms of reliability and performability as a function of observable parameters (e.g., topology, fault-tolerance, deadlines, communications, and failure categories). This process can give insight into further refinements of the original specification (i.e., identify potential failure processes and recovery actions). Relating the parameters needed for performability analysis to user level specifications is essential for realizing systems that meet user needs in terms of cost, functionality, and other nonfunctional requirements.

An example translation is given (in addition, some general examples of CSP → Petri net translations can be viewed in Appendix A). Based on this translation, we report both the discrete and continuous time Markovian analysis which provides reliability predictions for the candidate specification. The term “CSP-based” is used here to distinguish between the notation of Hoare’s original CSP and our textual representations which are similar to occum. Our CSP-based grammar does not restrict consideration of the properties of CSP (traces, refusal sets, livelock, etc.), but we are not considering those properties. We are only interested that the structural properties are preserved. We define performability as a measure of the system’s ability in meeting deadlines, in the presence of failures and variance in task execution times.
THE CHIMERA METHODOLOGY: DESIGNING DYNAMICALLY RECONFIGURABLE AND REUSABLE REAL-TIME SOFTWARE USING PORT-BASED OBJECTS
Authors: STEWART DAVID B. , KHOSLA PRADEEP K.
Published: September 2004

The Chimera Methodology is a software engineering paradigm that enables rapid development of real-time applications through use of dynamically reconfigurable and reusable software. It is targeted towards a distributed shared memory computing environment. The primary contribution of this research is the port-based object model of a real-time software component. The model is obtained by applying the port-automaton formal computational theory to object-based design. A finite state machine, detailed interface specifications, and a C-language template are used to define the port-based object. Tools to support the in-tegration, scheduling, and state variable communication between the objects have been developed and incorporated into the Chimera Real-Time Operating System. Techniques for verifying correctness and analyzing performance are also provided for configuration managers that integrate software designed using the port-based object model.
A FRAMEWORK FOR METHOD EVOLUTION AND BEHAVIOR CONSISTENCY IN OBJECT-ORIENTED DATABASES
Authors: TARI Z. , LI X.
Published: September 2004

This paper addresses the problem of method evolution in object-oriented databases. We propose a set of evolutionary operations that affect all parts of methods, the signature and the implementation. When a restructuring operation is applied to a schema, behavioral consistency is checked by constructing a proof of program correctness. Two levels of granularity for behavioral consistency are described. The first level relates to the evolution of methods in the context of class inheritance hierarchy and is concerned with the semantics of the polymorphism of methods. The second level relates to behavioral evolution in which the chain of calling relationships between methods is considered. Behavioral consistency is checked with a graph-based approach that deals with problems such as run-time type errors, side-effects, redundant methods, and unexpected behaviors.
REVERSE ENGINEERING GRAPHICAL REPRESENTATIONS OF X SOURCE CODE
Authors: CROSS II JAMES H. , DANNELLY R.STEPHEN
Published: September 2004

A technique for reverse engineering graphical user interfaces (GUIs) produced with Xtoolkit source code is presented. Two independent graphical representations are automatically generated to assist GUI programmers in the development, testing, maintenance, and reengineering of X-based GUI source code. This capability to generate both structural and behavioral views has the potential to provide major improvements in the comprehensibility of X source code. Whereas generating widget instance trees to describe the structure of an X interface is common, the automatic generation of dialogue state diagrams to describe the behavior of an X interface is unique to our technique. The intent of this paper is to provide insight into the functional details of our automated reverse engineering process for the benefit of other reverse engineering researchers and programming tool developers.
A DEVELOPMENT ENVIRONMENT FOR HARD REAL-TIME APPLICATIONS
Authors: ANCILOTTI PAOLO , BUTTAZZO GIORGIO , NATALE MARCO DI , SPURI MARCO
Published: September 2004

In this paper, we describe an integrated environment to assist the development of hard real-time applications. It includes an interactive graphic interface which allows the user to describe the application requirements according to three hierarchical levels: the application level, the component level, and the object level. The development model we propose is based on an iterative process in which the real-time scheduling support is considered since the beginning of the design phases.

Our graphic environment integrates several tools to analyse, test, and simulate the real-time application under development. In particular, the tools we have implemented are: a Design Tool, to describe the structure of the application, a Schedulability Analyser Tool (SAT), to verify off-line the feasibility of the schedule of a critical task set, a Scheduling Simulator, to test the average behaviour of the application, and a Maximum Execution Time (MET) estimator to bound the worst case duration of each task.
A SYSTEM FOR VISUALIZING AND DEBUGGING DISTRIBUTED REAL-TIME SYSTEMS WITH MONITORING SUPPORT
Authors: TSAI JEFFREY J.P. , BI YAO-DONG , YANG STEVE J.H.
Published: September 2004

Based on system execution traces, this paper presents a dynamic approach for visualizing and debugging timing constraint violations occurring in distributed real-time systems. The system execution traces used for visualization and debugging are collected during the execution of a target program in such a way that its run-time behavior is not interfered with. This is made possible by our non-interference distributed real-time monitoring system which is capable of collecting system’s run-time traces by monitoring and fetching the data passing through the internal buses of a target system. After the run-time data has been collected, the visualization and debugging activities then proceeded. The timing behavior of a target program is visualized as two graphs—the Colored Process Interaction Graph (CPIG) and the Dedicated Colored Process Interaction Graph (DCPIG). The CPIG depicts the timing behavior of a target program by graphically representing interprocess relationships during their communication and synchronization. The DCPIG can reduce visualization and debugging complexity by focusing on the portion of a target program which has direct or indirect correspondence with an imposed timing constraint. With the help of the CPIG and the DCPIG, a timing analysis method is used for computing the system-related timing statistics and analyzing the causes of timing constraint violations. A visualization and debugging system, called VDS, has been implemented using OpenWindows on Sun-4’s/UNIX workstations.
A METHODOLOGY AND SUPPORT TOOLS FOR ANALYSIS OF REAL-TIME SPECIFICATIONS
Authors: STUART DOUGLAS A. , MOK ALOYSIUS K. , JAHANIAN FARNAM
Published: September 2004

As software control of time-critical functions in embedded systems becomes more common, a means for the precise specification of their behavior and formal methods for analyzing system requirements become increasingly important. Modechart is a graphical specification language introduced to meet this need. The main focus of this paper is on methods and supporting tools for representing and reasoning about properties of time-critical systems specified in Modechart. The paper describes a verification methodology which takes advantage of the structuring inherent in a Modechart specification to determine whether a system specification satisfies the required properties. The paper also describes the implementation of a mechanical verifier, based on the proposed approach, which has been recently integrated as part of the Modechart Toolset prototype development environment from the Naval Research Lab [7].
MODELING AND DEVELOPING REAL-TIME CONCURRENT APPLICATIONS
Authors: BRUNO GIORGIO , AGARWAL RAKESH
Published: September 2004

The development of concurrent applications, which consist of several parallel, often distributed, activities that communicate and synchronize with each other, presents challenging logical and technological issues.

In the common practice, technological aspects, which are related to the definition of concurrent processes as well as of their interactions, often place constraints on the logical ones. Consequently, the flexibility that could be attained during design is reduced and, further, an actual implementation where both aspects are deeply intermixed is usually obtained.

This paper first presents an expressive and flexible language based on object-oriented high-level nets, which allows designers to naturally represent concurrency and synchronization. Then, it illustrates a powerful software engineering environment, CAB (Concurrent Applications Builder), which supports the building and the simulation/animation of models as well as the automatic generation of applications from models (by transforming the model’s objects into implementation processes).

A case study from an actual project for automatic toll collection in motor-ways is illustrated.
OBJECT ORIENTED DESIGN, MODULAR ANALYSIS, AND FAULT-TOLERANCE OF REAL-TIME CONTROL SOFTWARE SYSTEMS
Authors: PERKUSICH ANGELO , PERKUSICH MARIA L.B. , CHANG SHI-KUO
Published: September 2004

When specifying, designing and analyzing complex real-time systems, it is necessary to adopt a modular or compositional methodology. This methodology shall allow the designer the ability to verify local properties of individual modules or components in the system, and also shall allow the verification of the correct behavior of interacting components. The application of Petri nets for the modeling and verification of systems, at specification and design levels are well known. Despite the powerful structuring mechanisms available in the Petri nets theory for the construction of the model of complex systems, the designer is still likely to face the problem of state explosion, when analyzing and verifying large systems. In this work we introduce a modular analysis methodology for a kind of high level Petri nets named G-Nets.
USING DOMAIN KNOWLEDGE TO IMPROVE REVERSE ENGINEERING
Authors: GALL HARALD C. , KLÖSCH RENÉ R. , MITTERMEIR ROLAND T.
Published: September 2004

Integrating application domain knowledge into reverse engineering is an important step to overcome the shortcomings of conventional reverse engineering approaches that are based exclusively on information derivable from source code. In this paper, we show the basic concepts of a program transformation process from a conventional to an object-oriented architecture which incorporates extraneous higher-level knowledge in its process. To which degree this knowledge might stem from some general domain knowledge, and to which extent it needs to be introduced as application dependent knowledge by a human expert is discussed. The paper discusses these issues in the context of the architectural transformation of legacy systems to an object-oriented architecture.
OBJECT EXTENSIONS TO Z: A SURVEY
Authors: ACHEE B.L. , CARVER DORIS L.
Published: September 2004

Formal specification languages provide assistance to solving the problem of high maintenance costs caused by ineffective communication of a system’s requirements. Using a sound mathematical basis, a formal specification language provides a precise and definitive system description that can serve as a binding contract. Additionally, the integration of the object-oriented paradigm with a formal specification language provides increased potential for software reuse, conceptually cleaner specifications and a framework for defining interfaces. To this end, there has been significant work done to extend existing specification languages to allow object-oriented specifications.

This paper provides a comparison of such object-oriented specification languages, specifically, those extending Z. The paper is organized into five major sections. After a brief introduction to the concepts of formal specification languages and Z, a simple library system is defined and used as an example throughout the paper. Each of the object-oriented specification languages is introduced and classified as either using Z in an object-oriented style or providing a true object-oriented extension of Z. For each language, the specification of the example library system is presented following a brief overview of the language’s features. An in-depth comparison is made of each of the languages which provide a true object-oriented extension of Z.
REVERSE ENGINEERING OF COMPUTER-BASED CONTROL SYSTEMS
Authors: WELCH LONNIE R. , YU GUOHUI , RAVINDRAN BINOY , KURFESS FRANZ , HENRIQUES JORGE , WILSON MARK , SAMUEL ANTONIO L. , MASTERS MICHAEL W.
Published: September 2004

This article presents a process for the reengineering of computer-based control systems, and describes tools that automate portions of the process. The intermediate representation (IR) for capturing features of computer-based systems during reverse engineering is presented. A novel feature of the IR is that it incorporates the control system software architecture, a view that enables information to be captured at five levels of granularity: the program level, the task level, the package level, the subprogram level, and the statement level. A reverse engineering toolset that constructs the IR from Ada programs, displays the IR, and computes concurrency, communication and object-orientedness metrics is presented. Also described is the design of hypermedia techniques that enhance the usability of the reverse engineering tools.
A GRAPH-BASED SYSTEM FOR MANAGING CONFIGURATIONS OF ENGINEERING DESIGN DOCUMENTS
Authors: WESTFECHTEL BERNHARD
Published: September 2004

Due to increasing complexity of hardware and software systems, configuration management has been receiving more and more attention in nearly all engineering domains (e.g. electrical, mechanical, and software engineering). This observation has driven us to develop a domain-independent and adaptable configuration management model (called CoMa) for managing systems of engineering design documents. The CoMa model integrates composition hierarchies, dependencies, and versions into a coherent framework based on a sparse set of essential configuration management concepts. In order to give a clear and comprehensible specification, the CoMa model is defined in a high-level, multi-paradigm specification language (PROGRES) which combines concepts from various disciplines (database systems, knowledge-based systems, graph rewriting systems, programming languages). Finally, we also present an implementation which conforms to the formal specification and provides graphical, structure-oriented tools offering a bunch of sophisticated commands and operating in a heterogeneous environment.
A PERFORMANCE EVALUATION OF HEURISTICS-BASED TEST CASE GENERATION METHODS FOR SOFTWARE BRANCH COVERAGE
Authors: CHANG KAI H. , CROSS II JAMES H. , CARLISLE W.HOMER , LIAO SHIH-SUNG
Published: September 2004

Software testing is an important step in the development of complex systems. The construction of test cases using traditional methods usually requires considerable manual effort. QUEST/Ada—Query Utility Environment for Software Testing of Ada, is a prototype test case generation system that uses various heuristics-based approaches to generate test cases. The system, which is designed for unit testing, generates test cases by monitoring the branch coverage progress and intelligently modifying existing test cases to achieve additional coverage. Three heuristics-based approaches along with a random test case generation method were studied to compare their branch coverage performance. Although some constraints are imposed by the prototype, the framework provides a useful foundation for further heuristics-based test case generation research. The design of the system, the heuristic rules used in the system, and an evaluation of each rule’s performance are presented.
PARFORMAN—AN ASSERTION LANGUAGE FOR SPECIFYING BEHAVIOR WHEN DEBUGGING PARALLEL APPLICATIONS
Authors: AUGUSTON M. , FRITZSON P.
Published: September 2004

PARFORMAN (PARallel FORMal ANnotation language) is a high-level specification language for expressing intended behavior or known types of error conditions when debugging or testing parallel programs. Models of intended or faulty target program behavior can be succinctly specified in PARFORMAN. These models are then compared with the actual behavior in terms of execution traces of events, in order to localize possible bugs. PARFORMAN can also be used as a general language for expressing computations over target program execution histories.

PARFORM AN is based on a precise model of target program behavior. This model, called H-space (History-space), is formally defined through a set of general axioms about three basic relations, which may or may not hold between two arbitrary events: they may be sequentially ordered (SEQ), they may be parallel (PAR), or one of them might be included in another composite event (IN).

The general notion of composite event is exploited systematically, which makes possible more powerful and succinct specifications. The notion of event grammar is introduced to describe allowed event patterns over a certain application domain or language. Auxiliary composite events such as Snapshots are introduced to be able to define the notion “occurred at the same time” at suitable levels of abstraction. Finally, patterns and aggregate operations on events are introduced to make possible short and readable specifications. In addition to debugging and testing, PARFORMAN can also be used to specify profiles and performance measurements.
A KNOWLEDGE-ASSISTED APPROACH TO PARAMETERIZED REUSE
Authors: BHANSALI SANJAY
Published: September 2004

We describe a knowledge-based framework for software reuse based on parameterizing and instantiating a generic architecture. The reuse process consists of two phases: (1) an acquisition phase, which creates knowledge components representing problem classes, generic architectures, and the design process, followed by: (2) a synthesis phase, which reuses the knowledge components in instantiating a generic architecture for new applications. We illustrate the process using two case studies in two different domains. The distinguishing features of our approach include the use of both formal and informal representations and the use of knowledge to assist software designers in designing new systems. We present empirical evidence, based on the case studies to argue that the approach improves productivity and reliability.
ELIMINATING REDUNDANCY, CONFLICT, AND INCOMPLETENESS FROM KNOWLEDGE-BASED SYSTEMS
Authors: GAMBLE ROSE F. , SHAFT TERESA M.
Published: September 2004

The reliability of knowledge-based systems (KBSs) has been the subject of a great deal of recent research. Much of this research focuses on the verification of KBSs, specifically to eliminate redundant rules, conflicting rules, and to ensure that the KBS is complete. Often, verification is approached by testing the structural properties of the KBS after the rules have been defined. In this paper we take a different approach and show how the process of formal program derivation from software engineering can be applied to KBSs. The use of these techniques eliminates the need for post-development verification because program derivation guarantees that the KBS will not contain redundant rules, conflicting rules, or be incomplete. As such, verification concerns are addressed during development.
DESIGNING KNOWLEDGE-BASE TOOLS FOR PROGRAM COMPREHENSION: A COMPARISON OF EDATS & IMCA
Authors: WILDE NORMAN , DIETRICH SUZANNE W. , CALLISS FRANK W.
Published: September 2004

Since software engineers spend a large proportion of their time trying to understand computer programs, many tools have been proposed to help them with this task. The construction of such tools raises a series of specification and design issues and requires a careful choice among alternative user interfaces, tool architectures, and knowledge representations. This paper discusses the information needs of software engineers and describes and compares two such tools, the Extensible Dependency Analysis Tool Set (EDATS) and the Inter-Module Code Analysis system (IMCA). A case study is presented showing how each tool would be used to support typical program comprehension tasks. Though the two tools have quite similar objectives, their designs are radically different, leading to interesting contrasts in flexibility and ease of use.
OUTPUT SENSITIVE CONSTRUCTION OF THE DELAUNAY TRIANGULATION OF POINTS LYING IN TWO PLANES
Authors: BOISSONNAT JEAN-DANIEL , CÉRÉZO ANDRÉ , DEVILLERS OLIVIER , TEILLAUD MONIQUE
Published: September 2004

In this paper, we propose an algorithm to compute the Delaunay triangulation of a set [Formula: see text] of n points in 3-dimensional space when the points lie in 2 planes. The algorithm is output-sensitive and optimal with respect to the input and the output sizes. Its time complexity is O(n log n+t), where t is the size of the output, and the extra storage is O(n).
AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM
Authors: HEFFERNAN PAUL J.
Published: September 2004

In this paper we give optimal solutions for several versions of the two-guard problem. Given a simple polygon P with vertices s and t, the straight walk problem asks whether we can move two points monotonically on P from s to t, one clockwise and one counter-clockwise, such that the points are always co-visible. In the counter walk problem, both points move clockwise, one from s to t and the other from t to s. We provide Θ(n)-time constructive algorithms for both problems. We also give a Θ(n)-time decision algorithm for a version called the general walk problem. We obtain our results by examining the structure of the restrictions placed on the motion of the two points, and by employing properties of shortest paths and shortest path trees.
GEOMETRY OF BISECTORS FOR STRICTLY CONVEX DISTANCES
Authors: CORBALAN A.G. , MAZON M. , RECIO T.
Published: September 2004

In this paper we study some unexpected geometric properties of the family of bisector lines for a convex distance d, showing that bisectors do not always have an asymptotic line (Section 2). Moreover, although bisectors are homeomorphic to lines, pairs of them can exist intersecting infinitely many times (Section 3). This leads to the conclusion that convex distances are not always nice in the sense of Klein and Wood.7 On the other hand, we prove that distances d, having d-balls whose boundary is given by finitely many algebraic conditions, produce nice distances (Section 3).
APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
Authors: CHAN W.S. , CHIN F.
Published: September 2004

We improve the time complexities for solving the polygonal curve approximation problems formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n vertices with minimum number of line segments can be improved from O(n2 log n) to O(n2). The time complexity for approximating any polygonal curve with minimum error can also be improved from O(n2 log 2n) to O(n2 log n). We further show that if the curve to be approximated forms part of a convex polygon, the two problems can be solved in O(n) and O(n2) time respectively for both open and closed polygonal curves.
A LINEAR-TIME ALGORITHM FOR COVERING SIMPLE POLYGONS WITH SIMILAR RECTANGLES
Authors: BAR-YEHUDA REUVEN , BEN-HANOCH EYAL
Published: September 2004

We study the problem of covering a simple orthogonal polygon with a minimum number of (possibly overlapping) squares, all internal to the polygon. The problem has applications in VLSI mask generation, incremental update of raster displays, and image compression. We give a linear time algorithm for covering a simple polygon, specified by its vertices, with squares. Covering with similar rectangles (having a given x/y ratio) is an equivalent problem.
ON RECONSTRUCTING POLYHEDRA FROM PARALLEL SLICES
Authors: GITLIN CAROLE , O’ROURKE JOSEPH , SUBRAMANIAN VINITA
Published: September 2004

The problem of reconstructing a three-dimensional object from parallel slices has application in computer vision and medicine. Here we explore a specific existence question: given two polygons in parallel planes, is it always possible to find a polyhedron that has those polygons as faces, and whose vertices are precisely the vertices of the two polygons? We answer this question in the negative by providing an example of two polygons that cannot be connected to form a simple polyhedron. One polygon is a triangle, the other a somewhat complicated shape with spiraling pockets.
COMPUTATIONAL GEOMETRY COLUMN 27
Authors: O’ROURKE JOSEPH
Published: September 2004

The following new result is discussed: there is a perfect matching between the edges of any two triangulations of a finite set of points in the plane.
SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
Authors: CHEN JINDONG , HAN YIJIE
Published: September 2004

We present an algorithm for determining the shortest path between any two points along the surface of a polyhedron which need not be convex. This algorithm also computes for any source point on the surface of a polyhedron the inward layout and the subdivision of the polyhedron which can be used for processing queries of shortest paths between the source point and any destination point. Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. Our algorithm has time complexity O(n2) and space complexity Θ(n).
AN ALGORITHM FOR DRAWING A HIERARCHICAL GRAPH
Authors: EADES PETER , LIN XUEMIN , TAMASSIA ROBERTO
Published: September 2004

Hierarchical graphs appear in several graph drawing applications, where nodes are assigned layers for semantic reasons. More importantly, general methods for drawing directed graphs usually begin by transforming the input digraph into a hierarchical graph, then applying a hierarchical graph drawing algorithm.

This paper introduces the Degree Weighted Barycentre (DWB) algorithm for drawing hierarchical graphs. We show that drawings output by DWB satisfy several important aesthetic criteria: under certain connectivity conditions, they are planar, convex, and symmetric whenever such drawings are possible. The algorithm can be implemented as a simple Gauss — Seidel iteration.
CLASSIFICATION OF A POINT WITH RESPECT TO A POLYHEDRON VERTEX
Authors: JUAN-ARINYO ROBERT , VINACUA ÀLVAR , BRUNET PERE
Published: September 2004

Algorithms for solid boolean operations are strongly based on classifying points with respect to solids. Several algorithms for solving the point-in- polyhedron problem in Brep schemes have been proposed in the literature. In this context, this paper describes an algorithm for the classification of an arbitrary point in the region dose to a polyhe-dron vertex. The algorithm is simple, has linear complexity and does not suffer from singularities. It performs better than previous algorithms, which would be too expensive in this particular case. The proposed algorithm is especially well suited for Brep schemes including spatial data structures for geometric data localization and searching, for operations on octree and extended octree structures, and for boundary evaluation of CSG trees with polyhedral primitives. Its use in the general point-in-polyhedron classification problem is also discussed. The algorithm is based on an extension to point in unbounded polygon of the kinetic framework of Guibas et al.
MAXIMAL EMPTY ELLIPSOIDS
Authors: DWYER REX A. , EDDY WILLIAM F.
Published: September 2004

The task of finding the largest empty ellipsoid defined by a set of n point sites in Rd is investigated. It is shown that this can be solved by enumerating the facets of the convex hull of the sites projected onto a manifold in R[d(d+3)/2]. While O(n[d(d+3)/4]) time is required in the worst case, it is found that O(nd) suffices on average for independent uniform points when d is fixed and n increases without bound. The effects on the running time caused by imposing certain restrictions on the orientation and shape of the ellipsoid are also described. Applications to motion planning and design centering are considered briefly.
ROBUST SET OPERATIONS ON POLYHEDRAL SOLIDS: A FIXED PRECISION APPROACH
Authors: I.CHUBAREV ALEXANDER
Published: September 2004

An approach to the reliable boundary evaluation for polyhedral solids is proposed. The approach is based on the three ideas: an approximate evaluation of the Boolean operations is performed; precise calculations are performed at micro-level by using only exact numbers; triangulations are used for the boundary representation. Test examples illustrating efficiency of the approach are presented.
AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
Authors: SCHUIERER SVEN
Published: September 2004

We present a data structure that allows to preprocess a rectilinear polygon with n vertices such that, for any two query points, the shortest path in the rectilinear link or L1-metric can be reported in time O( log n+k) where k is the link length of the shortest path. If only the distance is of interest, the query time reduces to O( log n). Furthermore, if the query points are two vertices, the distance can be reported in time O(1) and a shortest path can be constructed in time O(1+k). The data structure can be computed in time O(n) and needs O(n) storage. As an application we present a linear time algorithm to compute the diameter of a simple rectilinear polygon w.r.t. the L1-metric.
ON THE DIFFICULTY OF DECIDING THE CONVEXITY OF POLYNOMIALS OVER SIMPLEXES
Authors: GUO BAINING
Published: September 2004

We analyze the complexity of deciding the convexity of polynomials over simplexes. For polynomials of degree four or higher, the decision problem requires accomplishing an NP-hard task; when the degrees of the polynomials are less than four, the problem can be solved in NC time.
A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET
Authors: BERKMAN OMER , SCHIEBER BARUCH , VISHKIN UZI
Published: September 2004

We present a parallel algorithm for finding the convex hull of a sorted point set. The algorithm runs in O( log log n) (doubly logarithmic) time using n/ log log n processors on a Common CRCW PRAM. To break the Ω( log n/ log log n) time barrier required to output the convex hull in a contiguous array, we introduce a novel data structure for representing the convex hull. The algorithm is optimal in two respects: (1) the time-processor product of the algorithm, which is linear, cannot be improved, and (2) the running time, which is doubly logarithmic, cannot be improved even by using a linear number of processors. The algorithm demonstrates the power of the “the divide-and-conquer doubly logarithmic paradigm” by presenting a non-trivial extension to situations that previously were known to have only slower algorithms.
COMPUTATIONAL GEOMETRY COLUMN 28
Authors: O’ROURKE JOSEPH
Published: September 2004

The Web directory of Computational Geometry Software is described.
AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
Authors: EVERETT HAZEL , ROBERT JEAN-MARC , VAN KREVELD MARC
Published: September 2004

This paper gives an optimal O(n log n+nk) time algorithm for constructing the levels 1,…, k in an arrangement of n lines in the plane. This algorithm is extended to compute these levels in an arrangement of n unbounded x-monotone polygonal convex chains, of which each pair intersects at most a constant number of times. We then show how these results can be used to solve several geometric optimization problems including the weak separation problem for sets of red and blue points or polygons, the maximum line transversal problem for sets of line segments, the densest hemisphere problem for sets of points on a sphere and the optimal corridor problem for sets of points in the plane. All of the algorithms are quality-sensitive; they run faster if the optimal solution is a good one.
A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
Authors: KLEIN ROLF , LINGAS ANDRZEJ
Published: September 2004

For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P’s vertices that is contained in P.
THE VISIBILITY COMPLEX
Authors: POCCHIOLA MICHEL , VEGTER GERT
Published: September 2004

We introduce the visibility complex (a 2-dimensional regular cell complex) of a collection of n pairwise disjoint convex obstacles in the plane. It can be considered as a subdivision of the set of free rays (i.e., rays whose origins lie in free space, the complement of the obstacles). Its cells correspond to collections of rays with the same backward and forward views. The combinatorial complexity of the visibility complex is proportional to the number k of free bitangents of the collection of obstacles. We give an O(n log n+k) time and O(k) working space algorithm for its construction. Furthermore we show how the visibility complex can be used to compute the visibility polygon from a point in O(m log n) time, where m is the size of the visibility polygon. Our method is based on the notions of pseudotriangle and pseudo-triangulation, introduced in this paper.
SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
Authors: MITCHELL JOSEPH S.B.
Published: September 2004

We give a subquadratic (O(n3/2+∊) time and O(n) space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worst case. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in time O( log n). The algorithm extends to the case of multiple source points, yielding a method to compute a Voronoi diagram with respect to the shortest path metric.
PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA
Authors: GARG ASHIM , GOODRICH MICHAEL T. , TAMASSIA ROBERTO
Published: September 2004

Rooted trees are usually drawn planar and upward, i.e., without crossings and with-out any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of rooted trees. We give tight upper and lower bounds on the area of various types of drawings, and provide linear-time algorithms for constructing optimal area drawings. Let T be a bounded-degree rooted tree with N nodes. Our results are summarized as follows:

• We show that T admits a planar polyline upward grid drawing with area O(N), and with width O(Nα) for any prespecified constant a such that 0<α<1.

• If T is a binary tree, we show that T admits a planar orthogonal upward grid drawing with area O (N log log N).

• We show that if T is ordered, it admits an O(N log N)-area planar upward grid drawing that preserves the left-to-right ordering of the children of each node.

• We show that all of the above area bounds are asymptotically optimal in the worst case.

• We present O(N)-time algorithms for constructing each of the above types of drawings of T with asymptotically optimal area.

• We report on the experimentation of our algorithm for constructing planar polyline upward grid drawings, performed on trees with up to 24 million nodes.
APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
Authors: CLARKSON KENNETH L. , EPPSTEIN DAVID , MILLER GARY L. , STURTIVANT CARL , TENG SHANG-HUA
Published: September 2004

We give a practical and provably good Monte Carlo algorithm for approximating center points. Let P be a set of n points in Rd. A point c∈Rd is a β-center point of P if every closed halfspace containing c contains at least βn points of P. Every point set has a 1/(d+1)-center point; our algorithm finds an Ω(1/d2)-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O( log 2d log log n) time. Our algorithm has been used in mesh partitioning methods and can be used in the construction of high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak ∊-nets. We derive a variant of our algorithm whose time bound is fully polynomial in d and linear in n, and show how to combine our approach with previous techniques to compute high quality center points more quickly.
SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
Authors: DEHNE FRANK , FABRI ANDREAS , RAU-CHAPLIN ANDREW
Published: September 2004

We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O(n/p)≫O(1) local memory and all processors are connected via some arbitrary interconnection network (e.g. mesh, hypercube, fat tree). We present O(Tsequential/p+Ts(n, p)) time scalable parallel algorithms for several computational geometry problems. Ts(n, p) refers to the time of a global sort operation.

Our results are independent of the multicomputer’s interconnection network. Their time complexities become optimal when Tsequential/p dominates Ts(n, p) or when Ts(n, p) is optimal. This is the case for several standard architectures, including meshes and hypercubes, and a wide range of ratios n/p that include many of the currently available machine configurations.

Our methods also have some important practical advantages: For interprocessor communication, they use only a small fixed number of one global routing operation, global sort, and all other programming is in the sequential domain. Furthermore, our algorithms use only a small number of very large messages, which greatly reduces the overhead for the communication protocol between processors. (Note however, that our time complexities account for the lengths of messages.) Experiments show that our methods are easy to implement and give good timing results.
CORRECTNESS PROOF OF A GEOMETRIC CONSTRAINT SOLVER
Authors: FUDOS IOANNIS , HOFFMANN CHRISTOPH M.
Published: September 2004

We present a correctness proof of a graph-directed variational geometric constraint solver. First, we prove that the graph reduction that establishes the sequence in which to apply the construction steps defines a terminating confluent reduction system, in the case of well-constrained graphs. For overconstrained problems there may not be a unique normal form. Underconstrained problems, on the other hand, do have a unique normal form.

Second, we prove that all geometric solutions found using simple root-selection rules must place certain triples of elements in the same topological order, no matter which graph reduction sequence they are based on. Moreover, we prove that this implies that the geometric solutions derived by different reduction sequences must be congruent. Again, this result does not apply to overconstrained problems.
CONSTRAINTS ON SIMPLE GEOMETRY IN TWO AND THREE DIMENSIONS
Authors: OWEN JOHN C.
Published: September 2004

We analyse the equations which result from imposing dimensional constraints in a number of simple geometric systems. In practical applications for CAD/CAM we are interested in mixed systems of geometric elements including points, curves and possibly surfuces in two and three dimensions. The properties of the equations which represent the simpler component systems provide considerable insight into the equations which are of practical importance.
CONSTRAINING A QUADRATIC RATIONAL BEZIER TO BE AN ELLIPTICAL ARC
Authors: MALRAISON PIERRE J.
Published: September 2004

Analytic constraint solvers have a limited set of available geometries, typically lines and circles. This paper examines a method for constraining the control net of a rational quadratic Bezier curve so that it is always an elliptical arc.
EVALUATING GEOMETRIC SENSITIVITIES AT SINGULAR AND NON-SINGULAR POINTS OF VARIATIONAL CAD MODELS FOR DESIGN OPTIMIZATION
Authors: CASALE MALCOLM S.
Published: September 2004

Much has been published on the topic of design optimization of mechanical components. Most of the research has concentrated on the finite element or boundary element part of the problem. Little effort has been applied to integrating design optimization with CAD. With the introduction of parametric and variational CAD, it is more desirable than ever to merge these technologies, i.e., to perform the analysis directly on the CAD geometry and to use the CAD parameters/dimensions as design variables. In this paper, one part of the problem is examined, the calculation of geometric sensitivities on variational CAD geometry. It is shown that for a well-conditioned set of constraint equations, the geometric sensitivities are easily obtained by a straight-forward application of the implicit function theorem. When the constraint equations become singular, the situation is more complex. The nature of singularities is explored, and a method, based on rational transformations that are common in algebraic curve tracing, is suggested to resolve singular points. It is shown that the geometric sensitivity is a natural by-product of the transformation. The paper concludes with some symbolic algebra software, a Mathematica package, that was found to be useful in the investigation.
DESIGNING MULTI-LINK ROBOT ARMS IN A CONVEX POLYGON
Authors: SUZUKI ICHIRO , YAMASHITA MASAFUMI
Published: September 2004

The problem of designing a k-link robot arm confined in a convex polygon that can reach any point in the polygon starting from a fixed initial configuration is considered. The links of an arm are assumed to be all of the same length. We present a necessary condition and a sufficient condition on the shape of the given polygon for the existence of such a k-link arm for various values of k, as well as necessary and sufficient conditions for rectangles, triangles and diamonds to have such an arm. We then study the case k=2, and show that, for an arbitrary n-sided convex polygon, in O(n2) time we can decide whether there exists a 2-link arm that can reach all inside points, and construct such an arm if it exists. Finally, we prove a lower bound and an upper bound on the number of links needed to construct an arm that can reach every point in a general n-sided convex polygon, and show that the two bounds can differ by at most one. The constructive proof of the upper bound thus provides a simple method for designing a desired arm having at most k+1 links when a minimum of k links are necessary, for any k≥3. The method can be implemented to run in O(n2) time.