A novel technique that uses the Moving Least Squares (MLS) method to interpolate sparse constraints over mesh surfaces is introduced in this paper. Given a set of constraints, the proposed technique constructs, directly on the surface, a smooth scalar field that interpolates or approximates the constraints. Three types of constraints: point-value, point-gradient and iso-contour, are introduced to provide flexible control of the scalar field design. Furthermore, the framework also provides the user control over the region of influence and rate of influence decrease of the constraints, through parameter adjustment. We demonstrate that the scalar fields resulted from this framework can be used in several mesh applications such as skin deformation, region selection and curve drawing.

Abstract We present an algorithm for the reconstruction of a surface with boundaries (including a non‐orientable one) in three dimensions from a sufficiently dense sample. It is guaranteed that the output is isotopic to the unknown sampled surface. No previously known algorithm guarantees isotopic or homeomorphic reconstruction of surfaces with boundaries. Our algorithm is surprisingly simple. It ‘peels’ slivers greedily from an α‐complex of a sample of the surface. No other post‐processing is necessary. We provide several experimental results from an implementation of our basic algorithm and also a modified version of it.

This paper presents an algorithm for sampling and triangulating a generic $C^2$-smooth surface $\Sigma\subset \mathbb{R}^3$ that is input with an implicit equation. The output triangulation is guaranteed to be homeomorphic to $\Sigma$. We also prove that the triangulation has well-shaped triangles, large dihedral angles, and a small size. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely, computations of the intersection points of a line and $\Sigma$, computations of the critical points in a given direction, and computations of certain silhouette points.

The medial axis of a shape is known to carry a lot of information about it. In particular a recent result of Lieutier establishes that every bounded open subset of Rn has the same homotopy type as its medial axis. In this paper we provide an algorithm that, given a sufficiently dense but not necessarily uniform sample from the surface of a shape with smooth boundary, computes a core for its medial axis approximation, in form of a piecewise linear cell complex, that captures the topology of the medial axis of the shape. We also provide a natural method to freely augment this core in order to enhance it geometrically all the while maintaining its topological guarantees. The definition of the core and its extension method are based on the steepest ascent flow induced by the distance function to the sample. We also provide a geometric guarantee on the closeness of the core and the actual medial axis.

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations, feature extractions and others. In most cases, the distance function induced by the surface is approximated by a discrete distance function induced by a discrete sample of the surface. The critical points of the distance function determine the topology of the set inducing the function. However, no earlier theoretical result has linked the critical points of the distance to a sampling of geometric structures to their topological properties. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface either lie very close to the surface or near its medial axis and this closeness is quantified with the sampling density. Based on this result, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sampling of a surface, approximates the surface geometrically, both in Hausdorff distance and normals, and captures its topology.

This paper presents an algorithm for sampling and triangulatinga smooth surface Σ ⊂ ℝ3 where the triangulation is homeomorphic to Σ. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface, computations of the critical points of some height functions defined on the surface and its restriction to a plane, and computations of some silhouette points. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth.

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.

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.

We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon.Its expected running time is linear in the size of the polygon.By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon.Our algorithm is considerably simpler than Chazelle's (1991) celebrated optimal deterministic algorithm and, hence, positively answers his question of whether a simpler randomized algorithm for the problem exists.The new algorithm can be viewed as a combination of Chazelle's algorithm and of non-optimal randomized algorithms due to Clarkson et al. (1991) andto Seidel (1991), with the essential innovation that sampling is performed on subchains of the initial polygonal chain, rather than on its edges.It is also essential, as in Chazelle's algorithm, to include a bottom-up preprocessing phase previous to the top-down construction phase.

IntroductionWe describe an approach for answering linear programming queries with respect to a set of n linear constraints in l~ d, for a fixed dimension d.Solutions to this problem had been given before by Ma-tou~ek (1993) using a multidimesional version of parametric search and by Chan (1996) using randomization and C!arkson's approach to linear programming.These previous approaches use data structures for halfspace-range emptiness queries and reporting queries, respectively.Our approach is a generalization of Chan's: it also uses halfspace-range reporting data structures, Clarkson's approach to linear programming, and avoids parametric search; unlike Chan's appraoch, it gives deterministic solutions without considerable additional preprocessing overhead.The new solution is as good or improves the previous solutions in all the range of storage space: with O(n ld/2j log °( 1) n) storage space, it achieves query time O(log c log d n), where c is a small constant independent from d, in comparison to O(log d+l n) for Matougek's data structure and O(n c log d) for Chan's; with O(n) storage space, it achieves, as Chan's data structure, query time O(nl-1/[d/2J20(l°g* n)) after O(nl~ -~) preprocessing, but without using randomization.Linear programming has received a great amount of attention in computational geometry because of its importance in applications and its relative simplicity.An important early discovery was that it can be performed in time linear in the number of constraints [16].Several alternative algorithms have been presented subsequently, both deterministic [3] and randomized [5,17,15].We consider the problem of linear programming queries: Given a set H of n linear constraints in ]~d (halfspaces), with the dimension d fixed, construct a data structure so that given a query linear function w (vector), the minimum of w restricted to N H = DhEH h can be determined efficiently.This was first solved "almost completely" by Matou~ek [13] using a multidimensional version of parametric search together with data structures for halfspace-range emptiness queries.Later, Chan [2] presented an alternative approach which through randomization reduced the problem to halfspace-range reporting queries.Chan's approach is conceptually simpler and achieves better query times in the case of small storage space; however, comparatively, it performs poorly when the storage space is large.An interesting and useful feature of Chan's approach is that it uses the half-space range reporting data structure as a black-box.

We present a deterministic algorithm for computing the diameter of a set of n points in R3; its running time O(n log n) is worst-case optimal.This improves previous deterministic algorithms by Ramos (1997) and Bespamyatnikh (1998), both with running time O(n log s n), and matches the running time of a randomized algorithm by Clarkson and Shot (1989).We also present a deterministic algorithm for computing the lower envelope of n functions of 2 variables, for a class of functions with certain restrictions; if the functions in the class have lower envelope with worst-case complexity O(f2(n)), the running time is O(f2(n)logn), in general, and O(f2(n)) when f2(n) = ~(n x+~) for any small fraction e > 0. The algorithms follow a divide-and-conquer approach based on deterministic sampling with the essential feature that planar graph separators are used to group subproblems in order to limit the growth of the total subproblem size.

Article Curve reconstruction: connecting dots with good reason Share on Authors: Tamal K. Dey Department of CSE, IIT Kharagpur, India 721302 Department of CSE, IIT Kharagpur, India 721302View Profile , Kurt Mehlhorn Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, D-66123 Saarbrücken, GermanyView Profile , Edgar A. Ramos Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, D-66123 Saarbrücken, GermanyView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 197–206https://doi.org/10.1145/304893.304972Online:13 June 1999Publication History 33citation434DownloadsMetricsTotal Citations33Total Downloads434Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

IntroductionWe describe the following data structures.For halfspace range reporting, in S-space using expected preprocessing time O(n log n), worst-case storage O(n log log n) and worst-case reporting time O(log n + k), where n is the number of data points and k the number of points reported; in d-space, with d even, using worst-case preprocessing time O(nlogn), storage O(n) and reporting time O(n1-1/Ld/21 log'n + k), where c is a constant.For ray shooting in a convex polytope in d-space determined by n facets, using deterministic preprocessing time 0( (n/ log n)ldi2J log' n) and storage 0( (n/ log n) ld/2J2c'os' ") and with query time O(logn).For ray shooting in arbitrary direction amon n hyperplanes using preprocessing O(nd/logld/2 n) and query time O(logn).B We also describe a randomized algorithm for constructing the k-level of n planes in S-space.In the case of planes dual to points in convex position, in which the size of the k-level is O(nk), the algorithm uses nearly optimal expected time O(n logn + nk2c'0g* ").By a standard geometric transformation the same time bound applies for the construction of the k-order Voronoi diagram of n sites in the plane.

We show that the well-known random incremental constructlon of Clarkson and Shor [14] can be adapted via gradations to provide efficient external-memory algorithms for some geomctric problems.In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line scgmcnts in the plane with K pairwise intersections, that requires G($$ logMjB Q + 5) expected disk accesses (I/OS), where M is the size of the available internal memory and B is the size of the block transfer.The approach is sufficiently general to obtain algorithms for the problems of 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched point location in a planar subdivision, which require an optimal expected number of I/OS and are olmplcr than the ones previously known.The results extend to a external-memory model with multiple disks.

Using a divide, prune, and conquer approach based on geometric partitioning, we obtain: (1) An output sensitive algorithm for computing a weighted Voronoi diagram in IL4 (the projection of certain polyhedra in R5) that runs in time O ((n + f) log3 f) where n is the number of sites and f is the number of output cells;

For a set S of n line segments in the plane, we give the first work-optimal deterministic parallel algorithm for con-structing their arrangement. It runs in O(log2 n) time using O(n logn + k) work in the EREW PRAM model, where k is the number of intersecting line segment pairs, and pro-vides a fairly simple divide-and-conquer alternative to the optimal sequential “plane-sweep ” algorithm of Chazelle and Edelsbrunner. Moreover, our method can be used to out-put all k intersecting pairs while using only O(n) working space, which solves an open problem posed by Chazelle and Edelsbrunner. We also describe a sequential algorithm for computing a single face in an arrangement of n line seg-ments that runs in O(n2(n) logn) time, which improves on a previous O(n log2 n) time algorithm. For collections of simplices in IRd, we give methods for constructing a set ofm = O(nd1 logc n+k) cells of constant descriptive complexity that covers their arrangement, where c> 1 is a constant and k is the number of faces in the arrangement. The construction is performed sequentially in O(m) time, or in O(logn) time using O(m) work in the EREW PRAM model. The covering can be augmented to answer point location queries in O(logn) time. In addition to supplying the first parallel methods for these problems, we improve on the previous best sequential methods by reducing the query times (from O(log2 n) in IR3 and O(log3 n) in IRd, d> 3), and also the size and construction cost of the covering (from O(nd1+ + k)). 1

We give fast randomized and deterministic parallel methods for constructing convex hulls in R/sup d/, for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have optimal work bounds (with high probability for the randomized methods). In particular, we show that the convex hull of n points in R/sup d/ can be constructed in O(log n) time using O(n log n+n/sup [d/2]/) work, with high probability. We also show that it can be constructed deterministically in O(log/sup 2/ n) time using O(n log n) work for d=3 and in O(log n) time using O(n/sup [d/2]/ log/sup c([d/2]-[d/2]/) n) work for d/spl ges/4, where c>0 is a constant which is optimal for even d/spl ges/4. We also show how to make our 3-dimensional methods output-sensitive with only a small increase in running time. These methods can be applied to other problems as well.>

G.H. Gonnet and P.A. Larson (1982) proposed a hashing scheme for external files which guarantees single access retrieval. They provided an asymptotic analysis of the scheme assuming uniform distribution of the signatures. This paper addresses an open problem posed by them in a second work (J. ACM, vol.35, no.1, p.161-84, 1988) about the performance of signatures having a skew distribution. An optimization problem is formulated to obtain the optimal signature distribution which maximizes the resulting load factor. Numerical results indicate that the optimal signature distribution results in significant reduction in the cost of insertions, which is of practical significance.>