Search

We propose algorithms to compute the Minkowski sum of two or more convex polytopes represented by their face lattices in R d. The time and space complexities of the pair-wise algorithm are O (d ω n m) and O (n + m + M) , respectively, where n , m and M are the face lattice sizes of the two summands and the sum, respectively, and ω ≈ 2. 37 , currently, is the matrix multiplication exponent. We also show that this algorithm is worst-case optimal for fixed d. Next, we generalize the pair-wise algorithm to r > 2 convex polytopes in R d. The time and space complexities of the r -summands generalized algorithm are O (d ω min { M N , r + ∏ i = 1 r N i }) and O (M + N) , respectively, where N i , 1 ≤ i ≤ r , is the size of i th summand, N = ∑ i = 1 r N i is the total input size and M is the output size of the Minkowski sum. We show that the r -summands generalized algorithm is worst-case optimal for fixed d ≥ 3 and r < d. [ABSTRACT FROM AUTHOR]

If a subset of vertices of a graph, designed in such a way that the remaining vertices have unique identification (usually called representations) with respect to the selected subset, then this subset is named as a metric basis (or resolving set). The minimum count of the elements of this subset is called as metric dimension. This concept opens the gate for different new parameters, like fault-tolerant metric dimension, in which the failure of any member of the designed subset is tolerated and the remaining subset fulfills the requirements of the resolving set. In the pattern of the resolving sets, a concept was introduced where the representations of edges must be unique instead of vertices. This concept was called the edge metric dimension, and this as well as the previously mentioned concepts belong to the idea of resolvability parameters in graph theory. In this paper, we find all the above resolving parametric sets of a convex polytope $ {F}_{♃} $ and compare their cardinalities.

The coefficients of the chain polynomial of a finite poset enumerate chains in the poset by their number of elements. The chain polynomials of the partition lattices and their standard type \(B\) analogues are shown to have only real roots. The real-rootedness of the chain polynomial is conjectured for all geometric lattices and is shown to be preserved by the pyramid and the prism operations on Cohen-Macaulay posets. As a result, new families of convex polytopes whose barycentric subdivisions have real-rooted \(f\)-polynomials are presented. An application to the face enumeration of the second barycentric subdivision of the boundary complex of the simplex is also included.Mathematics Subject Classifications: 05A05, 05A18, 05E45, 06A07, 26C10Keywords: Chain polynomial, geometric lattice, partition lattice, real-rooted polynomial, flag \(h\)-vector, convex polytope, barycentric subdivision

Let G be a graph and R = {r1, r2, ..., rk} be an ordered subset of vertices of G, if every two vertices of G have different representation r (v|R) = (d (v, r1) , d (v, r2) , ..., d (v, rk)) with respect to R, then R is said to be a metric-based resolving parameter or resolving set of G and its minimum cardinality is called the metric dimension of graph G. Metric dimension is considered as an important applied concept of graph theory especially in the localization of a network and also in the chemical graph theoretical study of molecular compounds. Therefore, it is hot topic to study for different families of graphs as well. Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming. In this paper, we determine the metric-based resolving parameter of line graph of a convex polytope Sn, and conclude that it has constant metric dimension but vary with the parity of n. This article presents a measurement of the line graph of a convex polytope, denoted as ( S n). The subsequent section provides the metric dimension of the resulting graph. There are two scenarios pertaining to the metric dimension of a selected graph with respect to the metric dimension. The metric dimension of even cycle-based convex polytopes is three, whereas for other values, the metric dimension is four. [ABSTRACT FROM AUTHOR]

A convex hull of finitely many points in the Euclidean space Rd is known as a convex polytope. Graphically, they are planar graphs i.e. embeddable on R2. Minimum dominating sets possess diverse applications in computer science and engineering. Locating-dominating sets are a natural extension of dominating sets. Studying minimizing locating-dominating sets of convex polytopes reveal interesting distance-dominating related topological properties of these geometrical planar graphs. In this paper, exact value of the locating-dominating number is shown for one infinite family of convex polytopes. Moreover, tight upper bounds on γl−d are shown for two more infinite families. Tightness in the upper bounds is shown by employing an updated integer linear programming (ILP) model for the locating-dominating number γl−d of a fixed graph. Results are explained with help of some examples. The second part of the paper solves an open problem in Khan (2023) [28] which asks to find a domination-related parameter which delivers a correlation coefficient of ρ>0.9967 with the total π-electronic energy of lower benzenoid hydrocarbons. We show that the locating-dominating number γl−d delivers such a strong prediction potential. The paper is concluded with putting forward some open problems in this area.

Most of the existing point-to-mesh distance query solvers, such as Proximity Query Package (PQP), Embree and Fast Closest Point Query (FCPW), are based on bounding volume hierarchy (BVH). The hierarchical organizational structure enables one to eliminate the vast majority of triangles that do not help find the closest point. In this paper, we develop a totally different algorithmic paradigm, named P2M, to speed up point-to-mesh distance queries. Our original intention is to precompute a KD tree (KDT) of mesh vertices to approximately encode the geometry of a mesh surface containing vertices, edges and faces. However, it is very likely that the closest primitive to the query point is an edge e (resp., a face f), but the KDT reports a mesh vertex υ instead. We call υ an interceptor of e (resp., f). The main contribution of this paper is to invent a simple yet effective interception inspection rule and an efficient flooding interception inspection algorithm for quickly finding out all the interception pairs. Once the KDT and the interception table are precomputed, the query stage proceeds by first searching the KDT and then looking up the interception table to retrieve the closest geometric primitive. Statistics show that our query algorithm runs many times faster than the state-of-the-art solvers. [ABSTRACT FROM AUTHOR]

High dimensional simulation of exchangeable multivariate Bernoulli distributions is a challenging and important issue in applications, for example in credit risk models. The main contributions of this paper are, even for high dimensions, algorithms to sample from exchangeable multivariate Bernoulli distributions and to determine the distributions and the bounds of a wide class of indices and measures of probability mass functions. Unlike the algorithms present in the literature the proposed method gives the possibility to simulate also from negatively correlated distributions. Such a method is based on the geometrical structure of the class of exchangeable Bernoulli probability mass functions, which are points in a convex polytope whose extremal points are analytically known. Estimation and testing are also addressed. • We provide an algorithm for high dimension simulation, estimation and testing. • We provide an algorithm for uniform sampling, also in high dimension. • We build the sampling distribution of relevant measures across the class. • We develop an example of application in finance (credit risk models). • We develop software for simulation and testing. [ABSTRACT FROM AUTHOR]

The paper is devoted to perfect and almost perfect homogeneous polytopes in Euclidean spaces. We have classified perfect and almost perfect polytopes among all regular polytopes and all semiregular polytopes except Archimedean solids and two four-dimensional Gosset polytopes. Also we have constructed some non-regular homogeneous polytopes that are (or are not) perfect and posed some unsolved questions. [ABSTRACT FROM AUTHOR]

Linear programming (LP) problems with uncertain objective function coefficients (OFCs) are treated in this paper. In such problems, the decision-maker would be interested in an optimal solution that has robustness against uncertainty. A solution optimal for all conceivable OFCs can be considered a robust optimal solution. Then we investigate an efficient method for checking whether a given non-degenerate basic feasible (NBF) solution is optimal for all OFC vectors in a specified range. When the specified range of the OFC vectors is a hyperbox, i. e., the marginal range of each OFC is given by an interval, it has been shown that the tolerance approach can efficiently solve the robust optimality test problem of an NBF solution. However, the hyper-box case is a particular case where the marginal ranges of some OFCs are the same no matter what values the remaining OFCs take. In real life, we come across cases where some OFCs' marginal ranges depend on the remaining OFCs' values. For example, the prices of products rise together in tandem with raw materials, the gross profit of exported products increases while that of imported products decreases because they depend on the currency exchange rates, and so on. Considering those dependencies, we consider a case where the range of the OFC vector is specified by a convex polytope. In this case, the tolerance approach to the robust optimality test problem of an NBF solution becomes in vain. To treat the problem, we propose an algorithm based on the outer approximation approach. By numerical experiments, we demonstrate how the proposed algorithm efficiently solves the robust optimality test problems of NBF solutions compared to a conventional vertex-listing method. [ABSTRACT FROM AUTHOR]

For a graph $ G $, we define a total $ k $-labeling $ \varphi $ is a combination of an edge labeling $ \varphi_e(x)\to\{1, 2, \ldots, k_e\} $ and a vertex labeling $ \varphi_v(x) \to \{0, 2, \ldots, 2k_v\} $, such that $ \varphi(x) = \varphi_v(x) $ if $ x\in V(G) $ and $ \varphi(x) = \varphi_e(x) $ if $ x\in E(G) $, then $ k = \, \mbox{max}\, \{k_e, 2k_v\} $. The total $ k $-labeling $ \varphi $ is an edge irregular reflexive $ k $-labeling of $ G $ if every two different edges $ xy $ and $ x^\prime y^\prime $, the edge weights are distinct. The smallest value $ k $ for which such labeling exists is called a reflexive edge strength of $ G $. In this paper, we focus on the edge irregular reflexive labeling of antiprism, convex polytopes $ \mathcal D_{n} $, $ \mathcal R_{n} $, and corona product of cycle with path. This study also leads to interesting open problems for further extension of the work.

Let 풫 be an n-dimensional convex polytope and let 풮 be a hypersurface in ℝ n . This paper investigates potentials to reconstruct 풫 , or at least to compute significant properties of 풫 , if the modulus of the Fourier transform of 풫 on 풮 with wave length λ, i.e., | ∫ 풫 e - i ⁢ 1 λ ⁢ 퐬 ⋅ 퐱 ⁢ 퐝퐱 | for ⁢ 퐬 ∈ 풮 , is given, λ is sufficiently small and 풫 and 풮 have some well-defined properties. The main tool is an asymptotic formula for the Fourier transform of 풫 with wave length λ when λ → 0 . The theory of X-ray scattering of nanoparticles motivates this study, since the modulus of the Fourier transform of the reflected beam wave vectors is approximately measurable on a half sphere in experiments. [ABSTRACT FROM AUTHOR]

Let 풫 and P ′ be 3-dimensional convex polytopes in R 3 and S ⊆ R 3 be a non-empty intersection of an open set with a sphere. As a consequence of a somewhat more general result it is proved that 풫 and P ′ coincide up to translation and/or reflection in a point if | ∫ P e - i ⁢ s ⋅ x ⁢ dx | = | ∫ P ′ e - i ⁢ s ⋅ x ⁢ dx | for all s ∈ S . This can be applied to the field of crystallography regarding the question whether a nanoparticle modelled as a convex polytope is uniquely determined by the intensities of its X-ray diffraction pattern on the Ewald sphere. [ABSTRACT FROM AUTHOR]

By using elementary yet interesting observations and refining techniques used in a recent work by Fei Xue et al., we present new upper bounds for covering functionals of convex polytopes in R n with few vertices. In these estimations, no information other than the number of vertices of the convex polytope is used. [ABSTRACT FROM AUTHOR]

Let $\Omega $ be a connected graph and for a given $l$ -ordered partition of vertices of a connected graph $\Omega $ is represented as $\beta =\{\beta _{1},\beta _{2}, {\dots },\beta _{l}\}$ . The representation of a vertex $\mu \in V(\Omega)$ is the vector $r(\mu |\beta)=(d(\mu,\beta _{1}),d(\mu,\beta _{2}), {\dots }, d(\mu,\beta _{l}))$ . The partition $\beta $ is a resolving partition for vertices of $\Omega $ if all vertices of $\Omega $ having the unique representation with respect to $\beta $ . The minimum number of $l$ in the resolving partition for $\Omega $ is known as the partition dimension of $\Omega $ and represented as $pd(\Omega)$ . Resolving partition and partition dimension have multipurpose applications in networking, optimization, computer, mastermind games and modeling of chemical structures. The problem of computing constant values of partition dimension is NP-hard so one can find sharp bound for the partition dimension of graph. In this article, we computed the upper bound for the convex polytopes $\mathbb {E}_{n},~\mathbb {S}_{n},~\mathbb {T}_{n},~\mathbb {G}_{n},~\mathbb {Q}_{n}$ and flower graph $f_{n\times 3}$ .

The authors give several new criteria to judge whether a simple convex polytope in a Euclidean space is combinatorially equivalent to a product of simplices. These criteria are mixtures of combinatorial, geometrical and topological conditions that are inspired by the ideas from toric topology In addition, they give a shorter proof of a well known criterion on this subject. [ABSTRACT FROM AUTHOR]

• Proved several lower and upper bounds on the Voronoi games on simple and convex polygons. Almost all are tight. • Devised optimal strategies for the games on convex polygons in poly-log linear and linear time for the players. • Extended the results on the bounds on the Voronoi games on polyhedra in R 3. • Polynomial-time strategies for both the players are devised for Voronoi games on convex polyhedra with restrictions. • Computed common intersection of ellipses in O (n log ⁡ n) time. The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients , where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B , respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P , respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k -round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i.e., there exist convex polygons such that no placement of B guarantees more than k clients in the k -round game. We also design O (n log 2 ⁡ n + m log ⁡ n) and O (n + m) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O (n log ⁡ n) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P , and the clients are on the polytope boundary. [ABSTRACT FROM AUTHOR]

The Suppes-Zanotti inequalities involving the joint expectations of just three binary quantum observables are (re-)derived by the hull computation of the respective correlation polytope. A min-max calculation reveals its maximal quantum violations correspond to a generalized Tsirelson bound. Notions of "contextuality" motivated by such violations are critically reviewed. [ABSTRACT FROM AUTHOR]

Polyrun is a Java library that provides methods for exploiting the bounded convex polytopes. Such polytopes define a space of feasible problem parameters with a set of linear constraints. The software makes available an implementation of the Hit-and-Run algorithm, which is the Markov Chain Monte Carlo method for an efficient uniform sampling from the convex polytopes. Moreover, it implements other procedures, such as Ball-Walk, Sphere-Walk, or Grid-Walk, for making random steps within a polytope. The software provides a Java Application Programming Interface (API) along with an intuitive Command Line Interface (CLI) for Hit-and-Run. It has been used to support real-world decision making in various application areas, including logistics, land use planning, nanotechnology, and energy. The software is free and open-source.

After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]

A convex hull of finitely many points in the Euclidean space R d is known as a convex polytope. Graphically, they are planar graphs i.e. embeddable on R 2 . Minimum dominating sets possess diverse applications in computer science and engineering. Locating-dominating sets are a natural extension of dominating sets. Studying minimizing locating-dominating sets of convex polytopes reveal interesting distance-dominating related topological properties of these geometrical planar graphs. In this paper, exact value of the locating-dominating number is shown for one infinite family of convex polytopes. Moreover, tight upper bounds on γ l - d are shown for two more infinite families. Tightness in the upper bounds is shown by employing an updated integer linear programming (ILP) model for the locating-dominating number γ l - d of a fixed graph. Results are explained with help of some examples. The second part of the paper solves an open problem in Khan (2023) [28] which asks to find a domination-related parameter which delivers a correlation coefficient of ρ > 0.9967 with the total π -electronic energy of lower benzenoid hydrocarbons. We show that the locating-dominating number γ l - d delivers such a strong prediction potential. The paper is concluded with putting forward some open problems in this area., Competing Interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2024 The Author(s).)

In this paper, we present an efficient improvement of gift wrapping algorithm for determining the convex hull of a finite set of points in ℝ n space, applying the best restricted area technique inspired from the Method of Orienting Curves (this method was used successfully in computational geometry by An and Trang in Numerical Algorithms59, 347–357 (2012), Optimization62, 975–988 (2013)). The numerical experiments on the sets of random points in two- and three-dimensional space show that the running time of our algorithm is faster than the gift wrapping algorithm and the newest modified one. [ABSTRACT FROM AUTHOR]

This paper is motivated by the difference between the classical principal component analysis (PCA) in a Euclidean space and the tropical PCA in a tropical projective torus as follows. In Euclidean space, the projection of the mean point of a given data set on the principle component is the mean point of the projection of the data set. However, in tropical projective torus, it is not guaranteed that the projection of a Fermat-Weber point of a given data set on a tropical polytope is a Fermat-Weber point of the projection of the data set. This is caused by the difference between the Euclidean metric and the tropical metric. In this paper, we focus on the projection on the tropical triangle (the three-point tropical convex hull), and we develop one algorithm and its improved version, such that for a given data set in the tropical projective torus, these algorithms output a tropical triangle, on which the projection of a Fermat-Weber point of the data set is a Fermat-Weber point of the projection of the data set. We implement these algorithms in R language and test how they work with random data sets. We also use R language for numerical computation. The experimental results show that these algorithms are stable and efficient, with a high success rate.

Problem 4.19 in Ziegler (Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)) asserts that every simple 3-dimensional polytope has the property that its dual can be constructed as the convex hull of points chosen from the facets of the original polytope. In this note we state a variant of this conjecture that requires the points to be a subset of the vertices of the original polytope, and provide a family of counterexamples for dimension d ≥ 3 . [ABSTRACT FROM AUTHOR]

The Orlicz Minkowski problem is a generalization of the L p Minkowski problem. For a class of appropriate functions and discrete measures that have no essential subspaces, the existence is demonstrated for the discrete Orlicz Minkowski problem. This is a non-trivial extension of the discrete L p Minkowski problem for p < 0 . [ABSTRACT FROM AUTHOR]

Inference procedure is a critical step of experimental researches to draw scientific conclusions especially in multiple testing. The false positive rate increases unless the unadjusted marginal p-values are corrected. Therefore, a multiple testing correction is necessary to adjust the p-values based on the number of tests to control type I error. We propose a multiple testing correction of MAX-test for a contingency table, where multiple χ2-tests are applied based on a truncated normal distribution (TND) estimation method by Botev. The table and tests are defined geometrically by contour hyperplanes in the degrees of freedom (df) dimensional space. A linear algebraic method called spherization transforms the shape of the space, defined by the contour hyperplanes of the distribution of tables sharing the same marginal counts. So, the stochastic distributions of these tables are transformed into a standard multivariate normal distribution in df-dimensional space. Geometrically, the p-value is defined by a convex polytope consisted of truncating hyperplanes of test's contour lines in df-dimensional space. The TND approach of the Botev method was used to estimate the corrected p. Finally, the features of our approach were extracted using a real GWAS data. [ABSTRACT FROM AUTHOR]

Let P1, ..., Pn and Q1, ..., Qn be convex polytopes in ℝn with Pi ⊆ Qi. It is well-known that the mixed volume is monotone: V(P1, ..., Pn) ≤ V(Q1, ..., Qn). We give two criteria for when this inequality is strict in terms of essential collections of faces as well as mixed polyhedral subdivisions. This geometric result allows us to characterize sparse polynomial systems with Newton polytopes P1, ..., Pn whose number of isolated solutions equals the normalized volume of the convex hull of P1 ∪ ... ∪ Pn. In addition, we obtain an analog of Cramer's rule for sparse polynomial systems. [ABSTRACT FROM AUTHOR]

This paper proposes a method for analyzing comprehensive theoretical digging performance of an excavator based on the convex polytope. The convex polytope is generated by using Newton–Euler's equations to establish dynamic relationships between the digging capability of the bucket and the driving capability of hydraulic cylinders with the consideration of the excavator tipping and slipping constraints, and is used to identify the excavator's output capability for digging forces and moments in the bucket force space. A set of indices for theoretically quantifying the digging capability, digging efficiency, as well as the matchability between the manipulator mechanism and the driving capability of hydraulic cylinders are proposed based on the polytope, and they are used to assess the digging trajectory characteristics and the dynamic digging performance of the entire excavator workspace. Two case studies for the excavator's digging performance assessment and optimal digging trajectory generation are conducted to test and validate this method. The proposed method contributes to comprehensively and deeply understand the design principles of an excavator, and shows the promising application prospect for guiding the design and development of new excavators. [ABSTRACT FROM AUTHOR]

Computing mixed volume of convex polytopes is an important problem in computational algebraic geometry. This paper establishes sufficient conditions under which the mixed volume of several convex polytopes exactly equals the normalized volume of the convex hull of their union. Under these conditions the problem of computing mixed volume of several polytopes can be transformed into a volume computation problem for a single polytope in the same dimension. We demonstrate through problems from real world applications that substantial reduction in computational costs can be achieved via this transformation in situations where the convex hull of the union of the polytopes has less complex geometry than the original polytopes. We also discuss the important implications of this result in the polyhedral homotopy method for solving polynomial systems. [ABSTRACT FROM AUTHOR]

We show that the general linear programming (LP) problem reduces in nearly linear time to the LP relaxations of many classical NP-hard combinatorial problems, assuming sparse encoding of instances. We distinguish two types of such reductions. In the first type (shown for set cover/packing, facility location, maximum satisfiability, maximum independent set, and multiway cut), the input linear program is feasible and bounded iff the optimum value of the LP relaxation attains a threshold, and then optimal solutions to the input linear program correspond to optimal solutions to the LP relaxation. In the second type (shown for exact set cover, three-dimensional matching, and constraint satisfaction), feasible solutions to the input linear program correspond to feasible solutions to the LP relaxations. Thus, the reduction preserves objective values of all (not only optimal) solutions. In polyhedral terms, every polytope in standard form is a scaled coordinate projection of the optimal or feasible set of the LP relaxation. Besides nearly linear-time reductions, we show that the considered LP relaxations are P-complete under log-space reductions, and therefore also hard to parallelize. These results pose a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations. [ABSTRACT FROM AUTHOR]

Abstract Given two convex d -polytopes P and Q in R d for d ⩾ 3 , we study the problem of bundling P and Q in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing P and a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d ⩾ 3. The running time is O (n (d − 1) ⌊ d + 1 2 ⌋) , where n denotes the number of vertices of P and Q. In particular, in dimension d = 3 , our algorithm runs in O (n 4) time. We also give an example of polytopes P and Q such that in the smallest container the translates of P and Q do not touch. [ABSTRACT FROM AUTHOR]

In this paper, we demonstrate the existence part of the discrete Orlicz Minkowski problem, which is a non-trivial extension of the discrete Lp Minkowski problem for 0 < p < 1. [ABSTRACT FROM AUTHOR]

For solving the advanced manufacturing fault diagnosis issue, a novel zonotopes estimation-based fault diagnosis algorithm is proposed in this paper. By using the intersection of the convex polytope and the tight strip, the fault diagnosis problem is changed into the analysis of the set membership outer bound computation. If the feasible set is detected empty, the set membership filters are designed. The minimal volume is also calculated and the selected zonotopes can be viewed as the approximate boundary. The simulation results show the effectiveness and practicability of the presented fault diagnosis algorithm. [ABSTRACT FROM AUTHOR]