1344352
Quality meshing for polyhedra with small angles
We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio ofmost output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Further, the mesh is graded, that is, edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. Unlike a previous algorithm, this algorithm is simple to implement as it avoids computing local feature sizes and protective zones explicitly. Our experimental results confirm our claims and show that few skinny tetrahedra remain.
29567956
Curve reconstruction from noisy samples
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.
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
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.
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.
8002270
Audio coding and image denoising based on the nonuniform modulated complex lapped transform
Xiong and Malvar recently introduced a nonuniform modulated complex lapped transform (NMCLT) with good time-localization and controllable frequency resolution by using an oversampled nonuniform filter bank to generate its real and the imaginary components. In this paper, we first show that oversampling in the NMCLT is not necessary in theory but a by-product of fast implementation in practice. We also point out that the amount of oversampling, which can be flexibly controlled, depends on the application. We then describe in detail the implementation of the inverse transform, which was not addressed clearly by Xiong and Malvar. We present the first applications of the NMCLT to audio coding and image denoising. A scalable audio coder has been implemented by controlling the amount of oversampling and exploiting redundancy among the NMCLT coefficients via predictive coding. Experimental results show that the audio coder reduces pre-echoes and improves the sound quality of audio clips with transient sounds. A simple denoising algorithm based on the NMCLT has also been devised to provide images with better visual quality than those obtained with wavelet-based soft thresholding.
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.
574471
Allocation and scheduling of real-time periodic tasks with relative timing constraints
Allocation problem has always been one of the fundamental issues of building the applications in real-time computing systems. For real-time applications, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and other synchronization constraints among them. Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task and the inter-task temporal relationships are specified across task periods. In this paper we consider the allocation and scheduling problem of the periodic tasks with such timing requirements. Given a set of periodic tasks, we consider the least common multiple (LCM) of the task periods. Each task is extended to several instances within the LCM. The scheduling window for each task instance is derived to satisfy the timing constraints. We develop a simulated annealing algorithm as the overall control algorithm. An example problem of the sanitized version of the Boeing 777 Aircraft Information Management System is solved by the algorithm. Experimental results show that the algorithm solves the problem in a reasonable time complexity.
8012254
Software architecture-based adaptation for Grid computing
Grid applications must increasingly self-adapt dynamically to changing environments. In most cases, adaptation has been implemented in an ad hoc fashion, on a per-application basis. This paper describes work which generalizes adaptation so that it can be used across applications by providing an adaptation framework. This framework uses a software architectural model of the system to analyze whether the application requires adaptation, and allows repairs to be written in the context of the architectural model and propagated to the running system. In this paper, we exemplify our framework by applying it to the domain of load-balancing a client-server system. We report on an experiment conducted using our framework, which illustrates that this approach maintains architectural requirements.
10474032
Dynamic quota-based admission control with sub-rating in multimedia servers
Abstract. An admission control algorithm for a multimedia server is responsible for determining if a new request can be accepted without violating the Quality of Service (QoS) requirements of the existing requests in the system. A novel quota-based admission control algorithm with sub-rating for two priority classes of requests is proposed in this study. The server capacity is divided into three partitions based on the quota values: one for each class of requests and one common pool shared by two classes of requests. Reward and penalty are adopted in the proposed system model. High-priority requests are associated with higher values of reward as well as penalty than low-priority ones. Given the characteristics of the system workload, the proposed algorithm finds the best partitions, optimizing the system performance based on the objective function of the total reward minus the total penalty. The sub-rating mechanism will reduce the QoS requirements of several low- priority clients, by cutting out a small fraction of the assigned server capacity, to accept a new high- priority client and to achieve a higher net earning value. A stochastic Petri-Net model is used to find the optimal quota values and two approximation approaches are developed to find sub-optimal settings. The experiment results show that the proposed algorithm performs better than one without sub-rating mechanism, and that the sub-optimal solutions found by the proposed approximation approaches are very close to optimal ones. The approximation approaches enable the algorithm to dynamically adjust the quota values, based on the characteristics of the system workload, to achieve higher system performance.