24680353
Facility Location Constrained to a Polygonal Domain
We develop efficient algorithms for locating an obnoxious facility in a simple polygonal region and for locating a desirable facility in a simple polygonal region. Many realistic facility location problems require the facilities to be constrained to lie in a simple polygonal region. Given a set S of m demand points and a simple polygon R of n vertices, we first show how to compute the location of an obnoxious facility constrained to lie in R, in O((m + n) logm + mlog n) time. We then show how to compute the location of a desirable facility constrained to lie in R, also in O((m + n) logm + mlog n) time. Both running times are an improvement over the known algorithms in the literature. Finally, our results generalize to the setting where the facility is constrained to lie within a set of simple polygons as opposed to a single polygon at a slight increase in complexity.
38367030
Partitions of complete geometric graphs into plane trees
Consider the following question: does every complete geometric graph K"2"n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the case of convex geometric graphs. It is well known that the complete convex graph K"2"n has a partition into n plane spanning trees. We characterise all such partitions. Second, we give a sufficient condition, which generalises the convex case, for a complete geometric graph to have a partition into plane spanning trees. Finally, we consider a relaxation of the problem in which the trees of the partition are not necessarily spanning. We prove that every complete geometric graph K"n can be partitioned into at most n-n/12 plane trees. This is the best known bound even for partitions into plane subgraphs.
1677550
Finding Specified Sections of Arrangements: 2D Results
Given a configuration C of geometric objects in R2 (called the input configuration), a target configurationT of geometric objects in R1, and a class S of allowable sectioning lines we consider in this paper many variations on the following problem: ‘Is there a line S∈S such that the section S∩C is equivalent by rigid motion to the target T?’
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 .
13523199
Approximate Range Mode and Range Median Queries
We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given indices i and j we can answer queries of the form: What is the mode or median label in the sequence of labels between indices i and j. Our results are on approximate versions of this problem. Using $O(\frac{n}{1-\alpha})$ space, our data structure can find in $O({\rm log}{\rm log}_\frac{1}{\alpha} n)$ time an element whose number of occurrences is at least α times that of the mode, for some user-specified parameter 0<α<1. Data structures are proposed to achieve constant query time for α=1/2,1/3 and 1/4, using storage space of O(n log n), O(n log log n) and O(n), respectively. Finally, if the elements are comparable, we construct an $O(\frac{n}{1-\alpha})$ space data structure that answers approximate range median queries. Specifically, given indices i and j, in O(1) time, an element whose rank is at least $\alpha \times \lfloor|j-i+1|/2\rfloor$ and at most $(2-\alpha)\times\lfloor|j-i+1|/2\rfloor$ is returned for 0<α<1.
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.
9029444
Workload-driven floorplanning for MIPS optimization
An approach to early floorplanning in which optimization of a CPU chip floorplan is done in the context of a program benchmark (workload) is presented. The methodology integrates workload-driven cycles-per-instruction estimation into the traditional cycle-time evaluation process implied by an (early) floorplanning tool. This effectively adds an extra dimension to the floorplanning optimization cost function and search space, allowing superior MIPS-tuning of the VLSI chip.<<ETX>>
42931174
Heuristic Rule-Based Program Transformations for Enhanced Vectorization
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.
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.
18129017
Validation of Turandot, a fast processor model for microarchitecture exploration
We describe the results in validating the performance projections from a parameterized trace-driven simulation model of a speculative out-of-order superscalar processor which has been developed with the objective of acting as a microarchitecture exploration tool. Because of its objective, the model-called Turandot-has been designed to deliver much higher simulation speed than what is achieved from detailed (RTL) processor models. We summarize the validation methodology used, and present experimental data gathered in the calibration of one processor organization modeled with Turandot against a detailed reference model. The results indicate that, on the average for SPECint95 sampled traces, Turandot is within 5% of the results reported by the reference model while exhibiting a speed-up factor of about 70.