15245491
Efficient Expected-Case Algorithms for Planar Point Location
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has been surprisingly little theoretical work on expected-case query time. 
 
We are given an n-vertex planar polygonal subdivision S satisfying some weak assumptions (satisfied, for example, by all convex subdivisions). 
 
We are to preprocess this into a data structure so that queries can be answered efficiently. We assume that the two coordinates of each query point are generated independently by a probability distribution also satisfying some weak assumptions (satisfied, for example, by the uniform distribution). 
 
In the decision tree model of computation, it is well-known from information theory that a lower bound on the expected number of comparisons is entropy(S). We provide two data structures, one of size O(n2) that can answer queries in 2 entropy(S) + O(1) expected number of comparisons, and another of size O(n) that can answer queries in (4 + O(1/√log n)) entropy(S)+O(1) expected number of comparisons. These structures can be built in O(n2) and O(n log n) time respectively. Our results are based on a recent result due to Arya and Fu, which bounds the entropy of overlaid subdivisions.
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.
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
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.
29567956
Curve reconstruction from noisy samples
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.
19385806
Lossy-to-lossless compression of medical volumetric data using three-dimensional integer wavelet transforms
We study lossy-to-lossless compression of medical volumetric data using three-dimensional (3-D) integer wavelet transforms. To achieve good lossy coding performance, it is important to have transforms that are unitary. In addition to the lifting approach, we first introduce a general 3-D integer wavelet packet transform structure that allows implicit bit shifting of wavelet coefficients to approximate a 3-D unitary transformation. We then focus on context modeling for efficient arithmetic coding of wavelet coefficients. Two state-of-the-art 3-D wavelet video coding techniques, namely, 3-D set partitioning in hierarchical trees (Kim et al., 2000) and 3-D embedded subband coding with optimal truncation (Xu et al., 2001), are modified and applied to compression of medical volumetric data, achieving the best performance published so far in the literature-both in terms of lossy and lossless compression.
2936245
On failure recoverability of client-server applications in mobile wireless environments
Analytical results for the Cdf of the failure recovery time for client-server applications in mobile wireless environments characterized by logging, and mobility handoff strategies for facilitating failure recovery are reported in the paper. The results can be applied to determine if a mobile application can satisfy its recoverability requirement upon a mobile host failure when operating under a set of parameter values characterizing the mobile application, the underlying client-server environment, and the logging & mobility handoff strategies adopted by the mobile application. Model parameters which affect the shape of the failure recovery time Cdf for two mobility handoff strategies, namely, Eager and Lazy, are identified, and their effects are analyzed, with numerical data and result interpretations given. A tradeoff analysis between the cost invested by these two mobility handoff strategies for maintaining the logging and checkpoint information before failure versus the return of investment in terms of improved failure recoverability is given, and the best checkpoint interval period that would yield the best return of investment for the eager mobility handoff strategy over the lazy strategy is identified.
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.
11053365
Making Self-Adaptation an Engineering Reality
In this paper, we envision a world where a software engineer could take an existing software system, specify, for a set of properties of interest, an objective, conditions for change, and strategies for their adaptation and, within a few man weeks, make that system self-adaptive where it was not before. We describe how our approach generalizes to different classes of systems and holds promise for cost-effective, dynamic system self-adaptation to become an engineering reality.
46276818
Reconciling the needs of architectural description with object-modeling notations
Complex software systems require expressive notations for representing their software architectures. Two competing paths have emerged. One is to use a specialized notation for architecture, an architecture description language (ADL). The other is to adapt a general-purpose modeling notation, such as UML. The latter has a number of benefits, including familiarity to developers, close mapping to implementations, and commercial tool support. However, it remains an open question as to how best to use object-oriented notations for architectural description, and, indeed, whether they are sufficiently expressive, as currently defined. In this paper, we take a systematic look at these questions, examining the space of possible mappings from ADLs into UML. Specifically, we describe (a) the principal strategies for representing architectural structure in UML; (b) the benefits and limitations of each strategy; and (c) aspects of architectural description that are intrinsically difficult to model in UML using the strategies.