Polyhedral circuits and their applications

DOI10.1007/978-3-030-57602-8_2MaRDI QIDQ2039640zbMATH OpenOpenAlexFDO

Authors Bin Fu, Pengfei Gu, Yuming Zhao

Publication date 5 July 2021

Full work available at URL https://arxiv.org/abs/1806.05797

zbMATH Keywords

lattice pointspolyhedral circuitsunionvolume

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We introduce polyhedra circuits. Each polyhedra circuit characterizes a geometric region in $mathbb{R}^d$. They can be applied to represent a rich class of geometric objects, which include all polyhedra and the union of a finite number of polyhedra. They can be used to approximate a large class of $d$-dimensional manifolds in $mathbb{R}^d$. Barvinok developed polynomial time algorithms to compute the volume of a rational polyhedra, and to count the number of lattice points in a rational polyhedra in a fixed dimensional space $mathbb{R}^d$ with a fix $d$. Define $T_V(d,,n)$ be the polynomial time in $n$ to compute the volume of one rational polyhedra, $T_L(d,,n)$ be the polynomial time in $n$ to count the number of lattice points in one rational polyhedra with $d$ be a fixed dimensional number, $T_I(d,,n)$ be the polynomial time in $n$ to solve integer linear programming time with $d$ be the fixed dimensional number, where $n$ is the total number of linear inequalities from input polyhedra. We develop algorithms to count the number of lattice points in the geometric region determined by a polyhedra circuit in $Oleft(ndcdot{r}_d(n)cdot{T}_V(d,,n)ight)$ time and to compute the volume of the geometric region determined by a polyhedra circuit in $Oleft(ncdot{r}_d(n)cdot{T}_I(d,,n)+r_d(n)T_L(d,,n)ight)$ time, where $n$ is the number of input linear inequalities, $d$ is number of variables and $r_d(n)$ be the maximal number of regions that $n$ linear inequalities with $d$ variables partition $mathbb{R}^d$.

Recommendations

• On Counting Lattice Points in Polyhedra
• On the Complexity of Computing the Volume of a Polyhedron
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Algorithms for polytope covering and approximation
• Effective lattice point counting in rational convex polytopes

Cites work

• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A threshold of ln n for approximating set cover
• An analytical expression and an algorithm for the volume of a convex polyhedron in \(R^ n\).
• An optimal algorithm for intersecting line segments in the plane
• Applications of random sampling in computational geometry. II
• Arrangements of planes in space
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Computing the volume, counting integral points, and exponential sums
• Computing Volumes of Polyhedra
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Counting lattice points by means of the residue theorem
• Effective lattice point counting in rational convex polytopes
• Finding simplicial subdivisions of polytopes
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 203206 (Why is no real title available?)
• scientific article; zbMATH DE number 1424290 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Lower Bounds for Approximation by Nonlinear Manifolds
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• On Counting Lattice Points in Polyhedra
• On the Complexity of Computing the Volume of a Polyhedron
• On the Division of the Plane by Lines
• Partition of Space
• Points entiers dans les polyèdres convexes
• Polytope Volume Computation
• Polyèdres et réseaux. (Polyhedra and lattices)
• Solving the knapsack problem via \(\mathbb Z\)-transform
• Sur un probl?me de g?om?trie diophantienne lin?aire. I. Poly?dres et r?seaux.
• The Ehrhart polynomial of the Birkhoff polytope
• The problem of calculating the volume of a polyhedron is enumerably hard
• Two Algorithms for Determining Volumes of Convex Polyhedra
• Why Johnny the developer can't work with public key certificates. An experimental study of OpenSSL usability

Cited in

(2)

• A polyhedral model for enumeration and optimization over the set of circuits
• scientific article; zbMATH DE number 3875297 (Why is no real title available?)

This page was built for publication: Polyhedral circuits and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2039640)