Computing the Integer Hull of Convex Polyhedral Sets

被引：0
作者：
Maza, Marc Moreno [1 ]
Wang, Linxiao [1 ]
机构：
[1] Univ Western Ontario, London, ON, Canada
来源：
COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING (CASC 2022) | 2022年 / 13366卷
关键词：
Polyhedral set; Integer hull; Parametric polyhedron; POINTS; ALGORITHM; LATTICE;
D O I：
10.1007/978-3-031-14788-3_14
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we discuss a new algorithm for computing the integer hull P-I of a rational polyhedral set P, together with its implementation in Maple and in the C programming language. Our implementation focuses on the two-dimensional and three-dimensional cases. We show that our algorithm computes the integer hull efficiently and can deal with polyhedral sets with large numbers of integer points.
引用
收藏
页码：246 / 267
页数：22
相关论文
共 50 条
[21]   An enhanced convex-hull edge method for flatness tolerance evaluation [J].
Lee, Moon-Kyu .
COMPUTER-AIDED DESIGN, 2009, 41 (12) :930-941
[22]   Convex Hull Aided Registration Method (CHARM) [J].
Fan, Jingfan ;
Yang, Jian ;
Zhao, Yitian ;
Ai, Danni ;
Liu, Yonghuai ;
Wang, Ge ;
Wang, Yongtian .
IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2017, 23 (09) :2042-2055
[23]   A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON [J].
Hu Zhanqi Li Yupeng Wang Jun Qiao Lei .
CADDM, 1997, (01) :61-64
[24]   A characterization theorem and an algorithm for a convex hull problem [J].
Kalantari, Bahman .
ANNALS OF OPERATIONS RESEARCH, 2015, 226 (01) :301-349
[25]   New algorithm to construct a planar convex hull [J].
Buitrago, Oscar Y. ;
Ramírez, Andrés L. ;
Britto, Rodrigo A. .
Informacion Tecnologica, 2015, 26 (04) :137-144
[26]   Convex Hull Calculation Approach Based on BST [J].
Matrokhin, Dmitry ;
Golovanov, Roman .
PROCEEDINGS OF THE 2018 IEEE CONFERENCE OF RUSSIAN YOUNG RESEARCHERS IN ELECTRICAL AND ELECTRONIC ENGINEERING (EICONRUS), 2018, :1549-1552
[27]   CONVEX HULL PROBLEM, LATTICE POINTS AND APPLICATIONS [J].
Fanache, Dumitru .
JOURNAL OF SCIENCE AND ARTS, 2011, (02) :163-175
[28]   Note on the complexity of the mixed-integer hull of a polyhedron [J].
Hildebrand, Robert ;
Oertel, Timm ;
Weismantel, Robert .
OPERATIONS RESEARCH LETTERS, 2015, 43 (03) :279-282
[29]   Generalized Differentiation of Probability Functions: Parameter Dependent Sets Given by Intersections of Convex Sets and Complements of Convex Sets [J].
van Ackooij, Wim ;
Perez-Aros, Pedro .
APPLIED MATHEMATICS AND OPTIMIZATION, 2022, 85 (01)
[30]   Doubling Convex Sets in Lattices: Characterizations and Recognition Algorithms [J].
Karell Bertet ;
Nathalie Caspard .
Order, 2002, 19 :181-207
12345