11217048
Computing nice sweeps for polyhedra and polygons
This paper does not deal with the sweeping paradigm itself; it deals with testing polygons and polyhedra to determine if they have a certain property. The properties that we consider are related to sweeping. We will test for a simple polygon or polyhedron if it can be swept by a line or plane such that every cross-section has a property like being convex or simply-connected. For example, to determine for a simple polygon (with interior) in the plane whether there is a sweep direction such that every cross-section is simplyconnected (a point, line segment, or empty) is the well-known question of determining whether a simple polygon is monotone in some direction. We solve two extensions of this problem in 3-space, and solve another extension in the plane. The first question we address applies to a polyhedron in 3space. We want to determine if there is a vector , such that if a sweeping plane with normal passes over , every cross-section of is convex. Toussaint [7] calls this property weakly monotonic in the convex sense. Obviously, for convex polyhedra, any vector gives only convex cross-sections during the sweep. For many nonconvex polyhedra no such vector exists. We give an time algorithm to find a vector if one exists, for a simple polyhedron with vertices. In case we allow more than one convex polygon in the cross-section, but no refle x vertices, we solve the problem in linear time. The second question deals with cross-sections of simple polyhedra that are always simply-connected. This property is called weakly monotonic [7]. Again the problem is to determine a vector , if one exists, such that any plane normal to intersects in a simple polygon. This cross-section may degenerate into a line segment, single point, or be empty. The cross-section may not become disconnected, nor may it contain a hole. We solve the problem in time. Thirdly, we consider sweeping a simple polygon with a line, but we allow the line to change its orientation. The problem is to determine if such a sweep exists that passes over the polygon , such that every cross-section is connected (generally, a single line segment). The problem is solved in quadratic time, also if we require additionally that the sweep line never goes back over any point of .
13164102
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
We present an optimal Θ(n)-time algorithm for the selection of a subset of the vertices of an n-vertex plane graph G so that each of the faces of G is covered by (i.e., incident with) one or more of the selected vertices. At most ⌊n/2⌋ vertices are selected, matching the worst-case requirement. Analogous results for edge-covers are developed for two different notions of "coverage". In particular, our linear-time algorithm selects at most n - 2 edges to strongly cover G, at most ⌊n/3⌋ diagonals to cover G, and in the case where G has no quadrilateral faces, at most ⌊n/3⌋ edges to cover G. All these bounds are optimal in the worst-case. Most of our results flow from the study of a relaxation of the familiar notion of a 2-coloring of a plane graph which we call a face-respecting 2-coloring that permits monochromatic edges as long as there are no monochromatic faces. Our algorithms apply directly to the location of guards, utilities or illumination sources on the vertices or edges of polyhedral terrains, polyhedral surfaces, or planar subdivisions.
7702094
On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
We introduce a family of directed geometric graphs, denoted GΛθ, that depend on two parameters λ and θ. For 0 ≤ θ < π/2 and 1/2 < λ < 1, the GΛθ graph is a strong t-spanner, with t = 1/(1-λ) cos θ. The out-degree of a node in the GΛθ graph is at most ⌊2π/ min(θ, arccos 1/2λ)⌋. Moreover, we show that routing can be achieved locally on GΛθ. Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters λ and θ indicate that for random point sets, the spanning ratio of GΛθ is better than the proven theoretical bounds.
7385007
On the sectional area of convex polytopes
A function j : %3 -+ ‘R is unimodal if it increases to a maximum value and then decreases. It is strictly unimodal if the increase and decrease are strict. To be precise, ~ is strictly unimodal iff for all reals z < y, the value o = min{~(z), j(y)} is either the global minimum or maximum of ~ or v < ~(z) for all z G (z, y). Unimodality is important for the design of efficient search algorithms because it permits prune-and-search strategies. E.g., Chazelle and Dobkin [2] showed that the perpendicular distance from a line 1 to an n-vertex convex polygon Q is bimodal. From this, unimodal functions can be constructed and the farthest point from t can be computed in O(log n) time. Unimodality can also simplify proofs. It was shown in 1973 that if A(z) is the length of the intersection of a convex polygon Q with the vertical line through Z, then A(x) is a strictly unimodal function [4]. We note that this generalizes to higher dimensions: the area in 7?3 (or volume in 7?~) of the intersection of a convex polytope K and a hyperplane h(z) = {(x,23, ..., Zd) I VZi G ‘R} is a strictly unimodal function A(x). (If the plane is defined by rotation instead of translation, then there are convex polytopes for which sectional area is not unimodal.) Prune-andsearch can be used to compute the intersection with maximum area (volume) in time proportional to the size of K, if K is stored with its complete facial lattice. For %33 our algorithm has an application to shape matching: Given convex polygons P and Q and a direction in which to translate P, one can find the translation
1023852
Coarse grained parallel maximum matching in convex bipartite graphs
We present a coarse grained parallel algorithm for computing a maximum matching in a convex bipartite graph G=(A,B,E). For p processors with N/p memory per processor, N=|A|+|B|,N/p/spl ges/p, the algorithm requires O(log p) communication rounds and O(T/sub sequ/(n/p,m/p)+n/p log p) local computation, where n=|A|,m=|B| and T/sub sequ/(n,m) is the sequential time complexity for the problem. For the BSP model, this implies O(log p) supersteps with O(gN+gn/p log p) communication cost and O(T/sub sequ/(n/p,m/p)+n/p log p) local computation.
1804621
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of threedimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.
9413783
Optimal Code Generation for Expressions on Super Scalar Machines
12711823
Parallel Simulation and Test of VLSI Array Logic
We consider the task of accelerating existing array logic CAD software by running them under parallel processing environments. We restrict our discussion to VLSI programmable logic arrays (PLAs); we present results based on fault simulation/test generation software implemented for PLAs. Due to the regular layout of such array logic, considerable parallelism is expected in any data processing problem involving these modules. However, depending on the underlying machine model, and the adopted programming model, varying levels of speed-up are exhibited. We first consider a typical pipelined, vector mainframe like the IBM 3090 VF. Through a combination of novel problem reformulation strategies, and educated coding guidelines for vector machines, we show how an original scalar program can be efficiently speeded up on such machines. The other machine model considered is that of a shared memory parallel processing system. Our results here are based on experiments run under an experimental multi-processor VM environment (VM/EPEX) which has been set up to predict the possible speed-up on a parallel processor such as RP3. The overall processing environment is assumed to be constrained to a scientific/engineering one, with Fortran as the primary coding medium and the hardware biased toward numerically-intensive applications.
17187148
Design of instruction set architectures for support of high-level languages
Conventional instruction sets or directly interpretable languages (DILs) have not been designed with high-level languages (HLLs) in mind. The modern design problem is to derive a space-time efficient DIL for a HLL processing system. In this paper, we present our approach to the problem of designing well-matched, space-time efficient DILs. A systematic, syntax- and semantics-directed DIL design methodology is presented. It calls for an incremental transformation of the source HLL, until a suitable target DIL is obtained. At the heart of the methodology is a canonic set of language transformations. An experimental study, involving several systematically derived DILs is carried out in order to characterize the relative merits and disadvantages of various sequences of transformations. Various space, time and interpretability trade-offs implied by the transformations are studied.
18281114
Performance and functional verification of microprocessors
We address the problem of verifying the correctness of pre-silicon models of a microprocessor. We touch on the latest advances in this area by considering two different aspects of the validation problem: (a) verifying the functional integrity of the model and (b) testing the model for timing accuracy at the architectural level. The latter area, that of performance verification, is of increasing importance in the design of server-class processor chips, with one or more high performance cores on a single die. We show how simulation-based test cases can be generated under a unified defect and coverage model to detect both performance and functional bugs. We present and discuss examples of such integrated validation methodologies used in real processor development projects.
2521753
A circuit level implementation of an adaptive issue queue for power-aware microprocessors
Increasing power dissipation has become a major constraint for future performance gains in the design of microproces sors In this paper we present the circuit design of an issue queue for a superscalar processor that leverages transmis sion gate insertion to provide dynamic low cost con gura bility of size and speed A novel circuit structure dynami cally gathers statistics of issue queue activity over intervals of instruction execution These statistics are then used to change the size of an issue queue organization on the y to improve issue queue energy and performance When applied to a xed full size issue queue structure the result is up to a reduction in energy dissipation The complexity of the additional circuitry to achieve this result is almost neg ligible Furthermore self timed techniques embedded in the adaptive scheme can provide a decrease in cycle time of the CAM array read of the issue queue when we change the adaptive issue queue size from entries largest possible to entries smallest possible in our design