The Experts below are selected from a list of 309 Experts worldwide ranked by ideXlab platform
Florent Dupont - One of the best experts on this subject based on the ideXlab platform.
-
Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps-that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in Ropf3. First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
-
Shape Modeling International - Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps—that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in ℝ(su3). First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
Hichem Barki - One of the best experts on this subject based on the ideXlab platform.
-
Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps-that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in Ropf3. First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
-
Shape Modeling International - Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps—that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in ℝ(su3). First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
Tudor Zamfirescu - One of the best experts on this subject based on the ideXlab platform.
-
Total Curvature and Spiralling Shortest Paths
Discrete and Computational Geometry, 2003Co-Authors: Imre Bárány, Krystyna Kuperberg, Tudor ZamfirescuAbstract:This paper gives a partial confirmation of a conjecture of Agarwal, Har-Peled, Sharir, and Varadarajan that the total curvature of a shortest path on the boundary of a Convex Polyhedron in R3 cannot be arbitrarily large. It is shown here that the conjecture holds for a class of polytopes for which the ratio of the radii of the circumscribed and inscribed ball is bounded. On the other hand, an example is constructed to show that the total curvature of a shortest path on the boundary of a Convex Polyhedron in R3 can exceed 2π. Another example shows that the spiralling number of a shortest path on the boundary of a Convex Polyhedron can be arbitrarily large.
-
Total curvature and spiralling shortest paths
arXiv: Metric Geometry, 2003Co-Authors: Imre Bárány, Krystyna Kuperberg, Tudor ZamfirescuAbstract:This paper gives a partial confirmation of a conjecture of P. Agarwal, S. Har-Peled, M. Sharir, and K. Varadarajan that the total curvature of a shortest path on the boundary of a Convex Polyhedron in the 3-dimensional Euclidean space cannot be arbitrarily large. It is shown here that the conjecture holds for a class of polytopes for which the ratio of the radii of the circumscribed and inscribed ball is bounded. On the other hand, an example is constructed to show that the total curvature of a shortest path on the boundary of a Convex Polyhedron can exceed 2 \pi. Another example shows that the spiraling number of a shortest path on the boundary of a Convex Polyhedron can be arbitrarily large.
Florence Denis - One of the best experts on this subject based on the ideXlab platform.
-
Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps-that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in Ropf3. First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
-
Shape Modeling International - Contributing vertices-based Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron
2009 IEEE International Conference on Shape Modeling and Applications, 2009Co-Authors: Hichem Barki, Florence Denis, Florent DupontAbstract:We present an original approach for the computation of the Minkowski sum of a non-Convex Polyhedron without fold and a Convex Polyhedron, without decomposition and union steps—that constitute the bottleneck of Convex decomposition-based algorithms. A non-Convex Polyhedron without fold is a Polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in ℝ(su3). First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-Convex-Convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum Polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-Convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.
Micha Sharir - One of the best experts on this subject based on the ideXlab platform.
-
on translational motion planning of a Convex Polyhedron in 3 space
SIAM Journal on Computing, 1997Co-Authors: Boris Aronov, Micha SharirAbstract:Let B be a Convex Polyhedron translating in 3-space amidst k Convex polyhedral obstacles A1,...,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums $P_i=A_i\oplus (-B)$, for i= 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and that it can be $\Omega(nk\alpha(k))$ in the worst case, where n is the total complexity of the individual Minkowski sums P1,...,Pk. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log k log n).