Abstract

D. Walkup and R. J-B Wets's lifting projection of convex polyhedra in 1969 is used for finding the Delaunay triangulation of a finite planar point set. In concrete, the finite planar point set is lifted on the surface of a paraboloid in R3\mathbb{R}^3 with center outside the convex hull of the set. To find quickly the lower convex hull of these points on the paraboloid a restricted region is proposed, thereby eliminating a large number of points to be calculated. The numerical experiments also show that our new version algorithm significantly reduces the running time.

Author information

Contact details are reproduced from the original publication and may be historical.

Phan Thanh An

Ho Chi Minh City University of Technology, Ho Chi Minh City, Vietnam
and: Vietnam National University, Ho Chi Minh City, Vietnam

thanhan@hcmut.edu.vn

Nam Dung Hoang

University of Science, Vietnam National University, Thanh Xuan, Hanoi, Vietnam

hoangnamdung@hus.edu.vn

Nguyen Kieu Linh

Posts and Telecommunications Institute of Technology, Nguyen Trai, Hanoi, Vietnam

linhnk@ptit.edu.vn

Keywords

  • Computing science
  • convex hull
  • Delaunay triangulation
  • extreme edge
  • gift-wrapping algorithm
  • lifting projection
  • lower convex hull
  • pattern recognition
  • restricted region
  • Voronoi diagram

Mathematics Subject Classification

52A15, 52B55; 52A30, 52B10, 68U05

References

  1. S. G. Akl, G. T. Toussaint: Efficient convex hull algorithms for pattern recognition applications, in: International Joint Conference on Pattern Recognition, Kyoto, Japan (1978) 483–487.Google Scholar
  2. P. T. An: Method of orienting curves for determining the convex hull of a finite set of points in the plane, Optimization 59/2 (2010) 175–179.https://doi.org/10.1080/02331930802434732Google Scholar
  3. P. T. An: Optimization Approaches for Computational Geometry, Publishing House for Science and Technology, Vietnam Academy of Science and Technology, Hanoi (2017).Google Scholar
  4. P. T. An: Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves, Optimization 67 (2018) 159–177.https://doi.org/10.1080/02331934.2017.1387260Google Scholar
  5. P. T. An, D. T. Giang: A direct method for determining the lower convex hull of a finite point set in 3D, in: Advanced Computational Methods for Knowledge Engineering, Proc. 3rd Int. Conf. Computer Science, Advances Intell. Syst. Computing 358 (2015) 15–26.https://doi.org/10.1007/978-3-319-17996-4_2Google Scholar
  6. P. T. An, N.-D. Hoang, N. K. Linh: An efficient improvement of gift-wrapping algorithm for computing the convex hull of a finite set of points in Rn, Numer. Algorithms 85 (2020) 1499–1518.https://doi.org/10.1007/s11075-020-00873-1Google Scholar
  7. P. T. An, L. H. Trang: A parallel algorithm based on convexity for the computing of Delaunay tessellation, Numer. Algorithm 59 (2012) 347–357.https://doi.org/10.1007/s11075-011-9493-2Google Scholar
  8. P. T. An, L. H. Trang: An efficient convex hull algorithm for finite point sets in 3D based on the Method of Orienting Curves, Optimization 62 (2013) 975–988.https://doi.org/10.1080/02331934.2011.623163Google Scholar
  9. F. Aurenhammer: Power diagrams: properties, algorithms and applications, SIAM J. Computing 16 (1987) 78–96.https://doi.org/10.1137/0216006Google Scholar
  10. P. Bhaniramka, R. Wenger, R. Crawfis: Isosurface construction in any dimension using convex hulls, IEEE Trans. Visualization Computer Graphics 10/2 (2004) 130–141.https://doi.org/10.1109/TVCG.2004.1260765Google Scholar
  11. G. E. Blelloch, J. C. Hardwick, G. L. Miller, D. Talmor: Design and implementation of a practical parallel Delaunay algorithm, Algorithmica 24 (1999) 243–269.https://doi.org/10.1007/PL00008262Google Scholar
  12. K. Q. Brown: Voronoi diagrams from convex hulls, Inf. Proc. Letters 9/5 (1979) 223–228.https://doi.org/10.1016/0020-0190(79)90074-7Google Scholar
  13. L. Demaret, A. Iske: Optimal N-term approximation by linear splines over anisotropic Delaunay triangulations, Math. Computation 84 (2015) 1241–1264.https://doi.org/10.1090/S0025-5718-2014-02908-6Google Scholar
  14. S. Fortune: A sweepline algorithm for the Voronoi diagrams, Algorithmica 2 (1987) 153–174.https://doi.org/10.1007/BF01840357Google Scholar
  15. L. J. Guibas, D. E. Knuth, M. Sharir: Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica 7 (1992) 381–413.https://doi.org/10.1007/BF01758770Google Scholar
  16. L. J. Guibas, J. Stolfi: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics 4 (1985) 74–123.https://doi.org/10.1145/282918.282923Google Scholar
  17. B. Joe: Construction of k-dimensional Delaunay triangulations using local transformations, SIAM J. Sci. Computing 14 (1993) 1415–1436.https://doi.org/10.1137/0914083Google Scholar
  18. M. Koiso, B. Palmer: Rolling construction for anisotropic Delaunay surfaces, Pacific J. Math. 267/1 (2008) 345–378.https://doi.org/10.2140/pjm.2008.234.345Google Scholar
  19. N. K. Linh, C. Song, J. Ryu, P. T. An, N.-D. Hoang, D.-S. Kim: QuickhullDisk: A faster convex hull algorithm for disks, Appl. Math. Computation 363 (2019) 124626.https://doi.org/10.1016/j.amc.2019.124626Google Scholar
  20. E. P. Mucke, I. Saias: Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, CompGeom’96, Philadelphia (1996) 274–283.https://doi.org/10.1145/237218.237396Google Scholar
  21. A. Okabe, B. Boots, K. Sugihara: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed., John Wiley & Sons, Hoboken (2000).https://doi.org/10.1002/9780470317013Google Scholar
  22. J. O’Rourke: Computational Geometry in C, 2nd ed., Cambridge University Press, Cambridge (1998).https://doi.org/10.1017/CBO9780511804120Google Scholar
  23. F. P. Preparata, M. I. Shamos: Computational Geometry, 2nd ed., Springer, New York (1985).https://doi.org/10.1007/978-1-4612-1098-6Google Scholar
  24. A. Przeworski: Delaunay cells for arrangements of flats in hyperbolic space, Pacific J. Math. 258/1 (2012) 223–256.https://doi.org/10.2140/pjm.2012.258.223Google Scholar
  25. M. D. Sikiric, A. Schuermann, F. Vallentin: Complexity and algorithms for computing Voronoi cells of lattices, Math. Computation 267 (2009) 1713–1731.https://doi.org/10.1090/S0025-5718-09-02224-8Google Scholar
  26. N. M. Sirakov, P. A. Mlsna: Search space partitioning using convex hull and concavity features for fast medical image retrieval, in: Proc. 2nd IEEE Int. Symp. Biomedical Imaging: Nano to Macro, Arlington (2004) 796–799.https://doi.org/10.1109/ISBI.2004.1398658Google Scholar
  27. A. Stepanova, J. M. G. Smith: Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms, Eur. J. Oper. Res. 218/3 (2012) 775–788.https://doi.org/10.1016/j.ejor.2011.11.031Google Scholar
  28. D. Walkup, R. J.-B. Wets: Lifting projections of convex polyhedra, Pacific J. Math. 28/2 (1969) 465–475.https://doi.org/10.2140/pjm.1969.28.465Google Scholar
  29. B. Yuan, C. L. Tan: Convex hull based skew estimation, Pattern Recognition 40/2 (2007) 456–475.https://doi.org/10.1016/j.patcog.2006.02.016Google Scholar

Suggested citation

P. T. An, N. D. Hoang, N. K. Linh. “The Lifting Projection of Convex Polyhedra for Finding Delaunay Triangulations.” Journal of Convex Analysis 29 (2022), No. 1, 143–156. https://doi.org/10.68381/jca29008

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.