5724521
Motorcycle Graphs and Straight Skeletons
We present a new algorithm to compute motorcycle graphs. It runs in $O(n \sqrt{n}\log n)$ time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected $O(n\sqrt{h+1}\log^2 n)$ time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in $O(n\sqrt{h+1}\log^2 n+r \sqrt{r} \log r)$ expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in $O(n\sqrt{n}\log^2n)$ expected time.
16505104
Approximate minimum weight Steiner triangulation in three dimensions
ApproximateMinimumWeightSteinerTriangulationinThreeDimensionsSiu-WingChengyTamal K. DeyAbstractDicultyofminimumweighttriangulationap oinsetinR2is well known.In this pap er we study the minimumweight triangulation problem for p olyhedra and general ob-stacle set in three dimensions.The weight of a triangulationin three dimensionsis assumed to b e the total surface areaof alltrianglesinvolved.It isshownthat ap olyhedronPof sizencan b e triangulated withO(2log) tetrahedra intimeO(n2log3) approximating the minimum weight trian-gulation ofPwithin a constant factor. No such prior resultisknown.Thesameb oundsalsoholdfor a3Dp ointsettriangulationallowingSteiner p oints.We consider anothersetting called general obstacle set, where the convex hull ofa set ofntrianglesis triangulatedconforming to the inputtriangles.In thiscase we show thatour metho dpro ducesa triangulati onof sizeO(n3log) in time) ap-proximating the weight of the minimum wt triangulationwithin a constant factor. This is a considerable improvementover theO(n6) b ound known for this case [3]. It is shown in[3] that minimumweighttriangulationisgo o dfor averagecase ray sho oting in three dimensions.This further substan-tiates the signi cance of our result.1Intro ductionThe minimum weight triangulation (MWT) problem ismostwell-knownintheplane,whereatriangulationwiththeminimumtotaledgelengthissoughtfora2Dp ointset.Theproblemisnotknowntob eNP-hard but no p olynomial-time algorithm is known.Re-centlyanapproximation algorithm withconstantfac-tor p erformance guarantee has b een designed for MWTby Levcop oulos and Krznaric[10].In another versionof theproblem Steinerp ointsareallowed andamini-mum weight Steinertriangulation (MWST)among allp ossibleSteinertriangulationsisdesired.Inparticu-lar, MWT is also a Steiner triangulation but with zeroSteiner p oints.Eppstein [8] showed how to approximatethe MWST of a 2Dp oint set within a constant factor.Instead of a 2Dp oint set, general inputs such as planarstraight line graphs (PSLG) have also b eenconsideredDepartment of Computer Science, HKUST, Hong Kong.e-mail: scheng@cs.ust.hkyDepartmentofCSE,I ITKharagpur,Kharagpur721302,India. e-mail: dey@cse.iitkgp.ernet.infor their applications in ray sho oting [3, 7]. A triangula-tion of a PSLG is the decomp osition of the convex hullof its verticeswhere the input line segments app ear asedges.When Steiner p oints are allowed these segmentsmay app ear as union of edges.Aronov and Fortune [3]observe that the technique of [8] applies to this case topro duce a p olynomial size triangulation approximatingMWSTwithinaconstantfactor.Inthesp ecialcasewhen the input PSLG is a p olygon p ossibly with holes,Cheng and Lee [7] presented an algorithm with b oth sizeand running timeO(nlog), whereis the numb er ofedges.Thetriangulationofap ointsetin3Disthedecomp osition of its convex hull into disjoint tetrahedra.The weight of the triangulation is the sum of the area ofthe triangles in it.Instead of p oint sets, the input mayconsist of a set of triangles with disjoint relative interior,acounterpartofPSLGin3D.Inthissettingcalledgeneral obstacle set, a minimum weight triangulation ofthe convex hull is sought where the input triangles haeto b e conformed.A sp ecial case arises when the inputtrianglesformtheb oundaryofap olyhedronwhoseinterioristob etriangulatedwithminimumweight.Noticethattheformulationofminimumweighttriangulation problem in these cases must allow Steinerp oints since there are arrangements of triangles in threespace such as the b oundary of Schonardt p olyhedron forwhich no triangulation is p ossible without Steiner p oints[12].WeconsiderMWSTproblemforthreedi erentcategories of inputs:p olyhedra, p oint sets, and generalobstaclesets.Of course,thisleaves op entheproblemof MWT of a 3Dp oint set since a p oint set can alwaysb e triangulated without Steiner p oints.ResultonMWSTprobleminthreedimensionsisscarce.Eppstein, in his pap er [8], acknowledges the dif- culty of the problem and observes the obstacles in gen-eralizing a metho d working in two dimension. When thelengths of the edges are taken as weights, he shows thatthemetho dcanb emo di edtopro duceanO(logn)-factorapproximation toMWSTofap ointset.How-ever,withareasoftrianglestakenastheweights,metho d could not b e generalized.Aronov and Fortune[3], building up on the technique of Eppstein showed hotopro duceanO(n6)sizetriangulation approximatingthe MWST of a general obstacle set.They argued that1
2549315
Quality meshing with weighted Delaunay refinement
Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra called slivers that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove silvers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including silvers. This success is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation. We show that an incremental weight pumping can be mixed seamlessly with vertex insertions in our weighted Delaunay refinement paradigm.
359856
Curve reconstruction from noisy samples
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases.We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.
2623430
Manifold reconstruction from point samples
We present an algorithm to "reconstruct" a smooth <i>k</i>-dimensional manifold <i>M</i> embedded in an Euclidean space R<sup>d</sup> from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to <i>M.</i> The running time is <i>O</i>(<i>n</i> log <i>n</i>) where <i>n</i> is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).
5215240
Sliver exudation
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that if the Delaunay triangulation has the ratio property introduced in [15] then there is an assignment of weights so the weighted Delaunay triangulation contains no slivers. We also give an algorithm to compute such a weight assignment.
6666618
Low-Power Design for Real-Time Systems
Real-time Systems often are located in the special environments where the power consumption is a big concern. Upon presence of timing constraints, the low power design on the real-time systems has significant impact on the performance as well as the schedulability of the systems. The system developers are facing the challenges for reducing the power consumption and meeting the timing constraints in the real-time systems.This paper represents one of few attempts to address the issue of the low power design on real-time systems. We present two power reduction methods: one is at the software compilation level and the other at the operating system level. Given a real-time program, an inter-instruction power reduction technique is proposed to transform the program to another one with lower power consumption. In addition, a scheduling algorithm for real-time operating systems is proposed to reschedule real-time programs when the execution time of the programs is changed. Therefore, the proposed scheduling algorithm works together with the proposed power reduction technique to make sure all programs meet their deadlines and to improve the system schedulability. We also evaluate the performance of the proposed inter-instruction reduction method by comparing it with the cold scheduling algorithm and show that the proposed method outperforms the cold scheduling algorithm and reduces more energy power.
1362947
Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications
Abstract We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for a suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has complexity O ( n 2 2 n M ), while the approximation solution has O ( n 4 M 2 ), where n is the number of processors in the system and M is the number of tasks in the graph.
30645069
Backtrack Routing and Priority-Based Wavelength Assignment in WDM Networks
In this paper, we consider two key problems in the WDM networks: the wavelengh assignment and routing problems. The objective of the problems is to minimize the request blocking rate. We propose two priority-based methods for the wavelength assignment problem: static and dynamic strategies. Based on the priority of an incoming request, the proposed methods allocate a wavelength among the available wavelengths for the given priority. Analytic models and simulations are presented for the proposed wavelength assignment methods so as to analyse the link blocking rate. The simulation results show that the link blocking rate by the dynamic strategy is less than that by the assignment strategy. We also develop a routing algorithm that works together with the proposed wavelength assignment methods to reduce the overall blocking rates. The proposed routing method maintains a routing tree for a given connection request. Based on the routing tree, the algorithm finds a route with one available wavelength for each link along the route. We compare the proposed routing method with the fixed routing and fixed alternate routing algorithms. The experiments show that the proposed routing algorithm performs better than the fixed routing and the alternate routing methods.
1009077
An architecture for coordinating multiple self-management systems
A common approach to adding self-management capabilities to a system is to provide one or more external control modules, whose responsibility is to monitor system behavior, and adapt the system at run time to achieve various goals (configure the system, improve performance, recover from faults, etc.). An important problem arises when there is more than one such self-management module: how can one make sure that they are composed to provide consistent and complementary benefits? In this paper we describe a solution that introduces a self-management coordination architecture and infrastructure to support such composition. We focus on the problem of coordinating self-configuring and self-healing capabilities, particularly with respect to global configuration and incremental repair. We illustrate the approach in the context of a self-managing video teleconference system that composes two preexisting adaptation modules to achieve synergistic benefits of both.
751641
Market-Based Resource Allocation for Information-Collection Scenarios
Dynamic decentralized resource allocation for information-collection can play a critical role in emergency scenarios. We explore two simplified scenarios for information-collection, and define market games for allocating resources to interdependent tasks. Experiments with a market game for disaster-response illustrate our general methodology for analyzing strategic interactions in such an environment.