Recognition of Digital Polyhedra with a Fixed Number of Faces

详细信息    查看全文

• 关键词：Pattern recognition ; Geometry of numbers ; Polyhedral separation ; Digital polyhedron ; Convex sets ; Polytopes
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9647
• 期：1
• 页码：415-426
• 全文大小：1,846 KB
• 参考文献：1.DGtal: Digital geometry tools and algorithms library. http://​dgtal.​org
  2.Aggarwal, A., Booth, H., O’Rourke, J., Suri, S., Yap, C.: Finding minimal convex nested polygons. Inf. Comput. 83(1), 98–110 (1989)MathSciNet CrossRef MATH
  3.Barvinok, A.I.: Lattice points and lattice polytopes. In: Handbook of Discrete and Computational Geometry, 2nd edn., pp. 153–176. Chapman and Hall/CRC, Boca Raton (2004)
  4.Beck, M., Robins, S.: Computing the Continuous Discretely. Undergraduate Texts in Mathematics. Springer, New York (2007)MATH
  5.Blichfeldt, H.F.: A new principle in the geometry of numbers, with some applications. Trans. Am. Math. Soc. 15, 227–235 (1914)MathSciNet CrossRef MATH
  6.Das, G., Joseph, D.: The complexity of minimum convex nested polyhedra. In: Proceedings of the 2nd Canadian Conference of Computational Geometry. pp. 296–301 (1990)
  7.Edelsbrunner, H., Preparata, F.: Minimum polygonal separation. Inf. Comput. 77(3), 218–232 (1988)MathSciNet CrossRef MATH
  8.Ehrhart, E.: Sur les polyédres rationnels homothétiques á n dimensions. Comptes Rendus de l’Académie des Sciences 254, 616–618 (1962)
  9.Haase, C., Ziegler, G.: On the maximal width of empty lattice simplices. Eur. J. Comb. 21, 111–119 (2000)MathSciNet CrossRef MATH
  10.Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)MathSciNet CrossRef MATH
  11.Megiddo, N.: Linear-time algorithms for linear programming in r\({}^{\text{3 }}\) and related problems. SIAM J. Comput. 12(4), 759–776 (1983)MathSciNet CrossRef MATH
  12.Megiddo, N.: On the complexity of polyhedral separability. Discrete Comput. Geom. 3(4), 325–337 (1988)MathSciNet CrossRef MATH
  13.Scarf, H.E.: Integral polyhedra in three space. Math. Oper. Res. 10, 403–438 (1985)MathSciNet CrossRef MATH
  14.Ziegler, G.: Lectures on Polytopes. Graduate Texts in Mathematics. Springer, New York (1995)CrossRef MATH
  
• 作者单位：Yan Gérard (16)
  
  16. LIMOS - UMR 6158 CNRS, Université d’Auvergne, Clermont-Ferrand, France
  
• 丛书名：Discrete Geometry for Computer Imagery
• ISBN：978-3-319-32360-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The main task of the paper is to investigate the question of the recognition of digital polyhedra with a fixed number of facets: given a finite lattice set \(S\subset \mathbb {Z}^d\) and an integer n, does there exist a polyhedron P of \(\mathbb {R}^d\) with n facets and \(P\cap \mathbb {Z}^d=S\)? The problem can be stated in terms of polyhedral separation of the set S and its complementary \(S^c=\mathbb {Z}^d / S\). The difficulty is that the set \(S^c\) is not finite. It makes the classical algorithms intractable for this purpose. This problem is overcome by introducing a partial order “is in the shadow of”. Its minimal lattice elements are called the jewels. The main result of the paper is within the domain of the geometry of numbers: under some assumptions on the lattice set S (if \(S\subset \mathbb {Z}^2\) is not degenerated or if the interior of the convex hull of \(S\subset \mathbb {Z}^d\) contains an integer point), it has only a finite number of lattice jewels. In this case, we provide an algorithm of recognition of a digital polyhedron with n facets which always finishes.