Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
84
result(s) for
"Cheng, Siu-Wing"
Sort by:
Delaunay Mesh Generation
Written by authors at the forefront of modern algorithms research, this book demonstrates the power and versatility of Delaunay meshers in tackling complex geometric domains ranging from polyhedra with internal boundaries to piecewise smooth surfaces. It is one of the first to integrate a vast amount of cutting-edge material on Delaunay triangulations. Covering both volume and surface meshes, the book offers a rigorous theoretical analysis of mesh generation methods while also showing how the algorithms work well in practice.
eBook
Implicit Manifold Reconstruction
Let \\[{{\\mathcal {M}}} \\subset \\mathbb {R}^d\\] be a compact, smooth and boundaryless manifold with dimension m and unit reach. We show how to construct a function \\[\\varphi :\\mathbb {R}^d \\rightarrow \\mathbb {R}^{d-m}\\] from a uniform \\[(\\varepsilon ,\\kappa )\\]-sample P of \\[{\\mathcal {M}}\\] that offers several guarantees. Let \\[Z_\\varphi \\] denote the zero set of \\[\\varphi \\]. Let \\[\\widehat{{{\\mathcal {M}}}\\] denote the set of points at distance \\[\\varepsilon \\] or less from \\[{\\mathcal {M}}\\]. There exists \\[\\varepsilon _0 \\in (0,1)\\] that decreases as d increases such that if \\[\\varepsilon \\le \\varepsilon _0\\], the following guarantees hold. First, \\[Z_\\varphi \\cap \\widehat{{\\mathcal {M}}}\\] is a faithful approximation of \\[{\\mathcal {M}}\\] in the sense that \\[Z_\\varphi \\cap \\widehat{{\\mathcal {M}}}\\] is homeomorphic to \\[{\\mathcal {M}}\\], the Hausdorff distance between \\[Z_\\varphi \\cap \\widehat{{\\mathcal {M}}}\\] and \\[{\\mathcal {M}}\\] is \\[O(m^{5/2}\\varepsilon ^{2})\\], and the normal spaces at nearby points in \\[Z_\\varphi \\cap \\widehat{{\\mathcal {M}}}\\] and \\[{\\mathcal {M}}\\] make an angle \\[O(m^2\\sqrt{\\kappa \\varepsilon })\\]. Second, \\[\\varphi \\] has local support; in particular, the value of \\[\\varphi \\] at a point is affected only by sample points in P that lie within a distance of \\[O(m\\varepsilon )\\]. Third, we give a projection operator that only uses sample points in P at distance \\[O(m\\varepsilon )\\] from the initial point. The projection operator maps any initial point near P onto \\[Z_\\varphi \\cap \\widehat{{\\mathcal {M}}}\\] in the limit by repeated applications.
Journal Article
Minimax Regret 1-Median Problem in Dynamic Path Networks
This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n3) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.
Journal Article
Approximate Shortest Descending Paths
We present an approximation algorithm for the shortest descending path problem. Given a source$s$and a destination$t$on a terrain, a shortest descending path from$s$to$t$is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from$s$to$t$ . Given any$\\varepsilon \\in (0,1)$ , our algorithm returns in$O(n^4\\log (n/\\varepsilon))$time a descending path of length at most$1+\\varepsilon$times the optimum. This is the first algorithm whose running time is polynomial in$n$and$\\log(1/\\varepsilon)$and independent of the terrain geometry. [PUBLICATION ABSTRACT]
Journal Article
Tangent Estimation from Point Samples
Let
M
be an
m
-dimensional smooth compact manifold embedded in
R
d
, where
m
is a constant known to us. Suppose that a dense set of points are sampled from
M
according to a Poisson process with an unknown parameter. Let
p
be any sample point, let
ϱ
be the local feature size at
p
, and let
ϱ
ε
be the distance from
p
to the
(
n
+
1
)
th nearest sample point for some
n
between
m
+
1
2
+
1
and
d
+
1
2
. Using the
n
sample points nearest to
p
, we can estimate the tangent space at
p
and it holds with probability
1
-
O
(
n
-
1
/
3
)
that the angular error is
O
(
ε
2
)
. The running time is bounded by the time to compute the thin SVD of an
n
×
d
+
1
2
matrix and the full SVD of an
n
×
d
matrix, which is usually
O
(
d
2
n
2
)
in practice. We implemented the algorithm and experimentally verified its effectiveness on both noiseless and noisy data.
Journal Article
Three-Dimensional Delaunay Mesh Generation
We propose an algorithm to compute a conforming Delaunay mesh of a bounded domain in R[superscript 3] specified by a piecewise linear complex. Arbitrarily small input angles are allowed, and the input complex is not required to be a manifold. Our algorithm encloses the input edges with a small buffer zone, a union of balls whose sizes are proportional to the local feature sizes at their centers. In the output mesh, the radius-edge ratio of the tetrahedra outside the buffer zone is bounded by a constant independent of the domain, while that of the tetrahedra inside the buffer zone is bounded by a constant depending on the smallest input angle. Furthermore, the output mesh is graded. Our work is the first that provides quality guarantees for Delaunay meshes in the presence of small input angles. [PUBLICATION ABSTRACT]
Journal Article
Edge Flips in Surface Meshes
Little theoretical work has been done on edge flips in surface meshes despite their popular usage in graphics and solid modeling to improve mesh equality. We propose the class of
(
ε
,
α
)
-meshes of a surface that satisfy several properties: the vertex set is an
ε
-sample of the surface, the triangle angles are no smaller than a constant
α
, some triangle has a good normal, and the mesh is homeomorphic to the surface. We believe that many surface meshes encountered in practice are
(
ε
,
α
)
-meshes or close to being one. We prove that flipping the appropriate edges can smooth a dense
(
ε
,
α
)
-mesh by making the triangle normals better approximations of the surface normals and the dihedral angles closer to
π
. Moreover, the edge flips can be performed in time linear in the number of vertices. This helps to explain the effectiveness of edge flips as observed in practice and in our experiments. A corollary of our techniques is that, in
R
2
, every triangulation with a constant lower bound on the angles can be flipped in linear time to the Delaunay triangulation.
Journal Article
Delaunay Refinement for Piecewise Smooth Complexes
We present a Delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions. The algorithm protects edges with weighted points to avoid the difficulty posed by small angles between adjacent input elements. These weights are chosen to mimic the local feature size and to satisfy a Lipschitz-like property. A Delaunay refinement algorithm using the weighted Voronoi diagram is shown to terminate with the recovery of the topology of the input. Guaranteed bounds on the aspect ratios, normal variation, and dihedral angles are also provided. To this end, we present new concepts and results including a new definition of local feature size and a proof for a generalized topological ball property.
Journal Article
Approximate Shortest Paths in Anisotropic Regions
Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with $n$ vertices. Let $\\rho\\geq 1$ be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any $\\varepsilon\\in(0,1)$ and for any two points $v_s$ and $v_d$, we give an algorithm that finds a path from $v_s$ to $v_d$ whose cost is at most $(1+\\varepsilon)$ times the optimal. Our algorithm runs in $O(\\frac{\\rho^2\\log \\rho}{\\varepsilon^2}n^3 \\log(\\frac{\\rho n}\\varepsilon))$ time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in $[1,\\rho]\\cup \\{\\infty\\}$, the time bound of our algorithm improves to $O(\\frac{\\rho\\log \\rho}{\\varepsilon}n^3 \\log(\\frac{\\rho n}\\varepsilon))$.
Journal Article