ContributionsThe boundary characteristic and the volume of lattice polyhedra

The boundary characteristic — introduced by Ding and Reay — is a functional defined for a given planar tiling which associates with a given lattice figure, some integer. It appeared to be a very useful parameter to determine the area of lattice figures in the planar tilings with congruent regular polygons. The purpose of this paper is to extend the notion of the boundary characteristic to lattice polyhedra in ³. Studying some of its properties we show, in particular, that it can be applied to determine the volume of lattice polyhedra.     

The boundary characteristic and the volume of lattice polyhedra

The boundary characteristic — introduced by Ding and Reay — is a functional defined for a given planar tiling which associates with a given lattice figure, some integer. It appeared to be a very useful parameter to determine the area of lattice figures in the planar tilings with congruent regular polygons. The purpose of this paper is to extend the notion of the boundary characteristic to lattice polyhedra inR³. Studying some of its properties we show, in particular, that it can be applied to determine the volume of lattice polyhedra.     

Lattice polygons with two interior lattice points

A lattice point in the plane is a point with integer coordinates. A lattice segment is a line segment whose endpoints are lattice points. A lattice polygon is a simple polygon whose vertices are lattice points. We find all convex lattice polygons in the plane up to equivalence with two interior lattice points.     

Densest translational lattice packing of non-convex polygons

A translational lattice packing of k polygons P₁,P₂,P₃,…,P_k is a (non-overlapping) packing of the k polygons which is replicated without overlap at each point of a lattice i₀v₀+i₁v₁, where v₀ and v₁ are vectors generating the lattice and i₀ and i₁ range over all integers. A densest translational lattice packing is one which minimizes the area |v₀×v₁| of the fundamental parallelogram. An algorithm and implementation is given for densest translational lattice packing. This algorithm has useful applications in industry, particularly clothing manufacture.     

Facial structures of lattice path matroid polytopes

A lattice path matroid is a transversal matroid corresponding to a pair of lattice paths on the plane. A matroid base polytope is the polytope whose vertices are the incidence vectors of the bases of the given matroid. In this paper, we study the facial structures of matroid base polytopes corresponding to lattice path matroids. In the case of a border strip, we show that all faces of a lattice path matroid polytope can be described by certain subsets of deletions, contractions, and direct sums. In particular, we express them in terms of the lattice path obtained from the border strip. Subsequently, the facial structures of a lattice path matroid polytope for a general case are explained in terms of certain tilings of skew shapes inside the given region.     

A lattice Boltzmann model for blood flows

A lattice Boltzmann model for blood flows is proposed. The lattice Boltzmann Bi-viscosity constitutive relations and control dynamics equations of blood flow are presented. A non-equilibrium phase is added to the equilibrium distribution function in order to adjust the viscosity coefficient. By comparison with the rheology models, we find that the lattice Boltzmann Bi-viscosity model is more suitable to study blood flow problems. To demonstrate the potential of this approach and its suitability for the application, based on this validate model, as examples, the blood flow inside the stenotic artery is investigated.     

Multidimensional pseudo-spectral methods on lattice grids

When multidimensional functions are approximated by a truncated Fourier series, the number of terms typically increases exponentially with the dimension s. However, for functions with more structure than just being L²-integrable, the contributions from many of the Ns terms in the truncated Fourier series may be insignificant. In this paper we suggest a way to reduce the number of terms by omitting the insignificant ones. We then show how lattice rules can be used for approximating the associated Fourier coefficients, allowing a similar reduction in grid points as in expansion terms. We also show that using a lattice grid permits the efficient computation of the Fourier coefficients by the FFT algorithm. Finally we assemble these ideas into a pseudo-spectral algorithm and demonstrate its efficiency on the Poisson equation.     

On lattice sums and Wigner limits

Wigner limits are given formally as the difference between a lattice sum, associated to a positive definite quadratic form, and a corresponding multiple integral. To define these limits, which arose in work of Wigner on the energy of static electron lattices, in a mathematically rigorous way one commonly truncates the lattice sum and the corresponding integral and takes the limit along expanding hypercubes or other regular geometric shapes. We generalize the known mathematically rigorous two- and three-dimensional results regarding Wigner limits, as laid down in [3], to integer lattices of arbitrary dimension. In doing so, we also resolve a problem posed in [6, Chapter 7]. For the sake of clarity, we begin by considering the simpler case of cubic lattice sums first, before treating the case of arbitrary quadratic forms. We also consider limits taken along expanding hyperballs with respect to general norms, and connect with classical topics such as Gauss's circle problem. Appendix A is included to recall certain properties of Epstein zeta functions that are either used in the paper or serve to provide perspective.     

An extremal result on convex lattice polygons

The diameter of a convex set C is the length of the longest segment in C, and the local diameter at a point p is the length of the longest segment which contains p. It is easy to see that the local diameter at any point equals at least half of the diameter of C.

This paper looks at the analogous question in a discrete setting; namely we look at convex lattice polygons in the plane. The analogue of Euclidean diameter is lattice diameter, defined as the maximal number of collinear points from a figure. In this setting, lattice diameter and local lattice diameter need not be related. However, for figures of a certain size, the local lattice diameter at any point must equal at least (n − 2)/2, where n is the lattice diameter of the figure. The exact minimal size for which this result holds is determined, as a special case of an exact combinatorial formula.     

Realizable Quadruples for Hex-polygons

There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ² with vertices in the integral lattice ℤ². Geometrically, ℤ² is the set of corners of a tiling of ℝ² by unit squares. Denote by H the set of corners of a tiling of the plane by regular hexagons of unit area and call a polygon P a Hex-polygon or an H-polygon if all vertices of P are in H. Our purpose is to study several combinatorial properties of H-polygons that are analogous to properties of lattice polygons. In particular we aim to find some relationships between the numbers b and i of points from H on the boundary and in the interior of an H-polygon P with the numbers v and c of vertices and the so-called boundary characteristic of P. We also pose three open problems dealing with convex Hex-polygons.     

On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

An efficient and accurate lattice for pricing derivatives under a jump-diffusion process

Derivatives are popular financial instruments whose values depend on other more fundamental financial assets (called the underlying assets). As they play essential roles in financial markets, evaluating them efficiently and accurately is critical. Most derivatives have no simple valuation formulas; as a result, they must be priced by numerical methods such as lattice methods. In a lattice, the prices of the derivatives converge to theoretical values when the number of time steps increases. Unfortunately, the nonlinearity error introduced by the nonlinearity of the option value function may cause the pricing results to converge slowly or even oscillate significantly. The lognormal diffusion process, which has been widely used to model the underlying asset’s price dynamics, does not capture the empirical findings satisfactorily. Therefore, many alternative processes have been proposed, and a very popular one is the jump-diffusion process. This paper proposes an accurate and efficient lattice for the jump-diffusion process. Our lattice is accurate because its structure can suit the derivatives’ specifications so that the pricing results converge smoothly. To our knowledge, no other lattices for the jump-diffusion process have successfully solved the oscillation problem. In addition, the time complexity of our lattice is lower than those of existing lattice methods by at least half an order. Numerous numerical calculations confirm the superior performance of our lattice to existing methods in terms of accuracy, speed, and generality.     

Covering grids and orthogonal polygons with periscope guards

The problem of finding minimum guard covers is NP-hard for simple polygons and open for simple orthogonal polygons. Alternative definitions of visibility have been considered for orthogonal polygons. In this paper we try to determine the complexity of finding guard covers in orthogonal polygons by considering periscope visibility. Under periscope visibility, two points in an orthogonal polygon are visible if there is an orthogonal path with at most one bend that connects them without intersecting the exterior of the polygon. We show that finding minimum periscope guard (as well as k-periscope and s-guard) covers is NP-hard for 3-d grids. We present an O(n³) algorithm for finding minimum periscope guard covers for simple grids and discuss how to extend the algorithm to obtain minimum k-periscope guard covers. We show that this algorithm can be applied to obtain minimum periscope guard covers for a class of simple orthogonal polygon in O(n³).     

Region configurations for realizability of lattice Piecewise-Linear models

Continuous Piecewise-Linear (PWL) functions can be represented by a scheme that selects adequately the linear components of the function without considering explicitly the boundaries. The representation method based on the Lattice Theory, that we call the lattice PWL model, is a form that fits that scheme. In this paper, two domain partitions are proposed that give rise to region configurations practically meaningful for the realizability of lattice models. In one of those partitions, each region is uniquely determined by one of the linear function. The other region configuration is derived from the rearrangement in ascending order of the linear components. Both configurations are discussed and connected with the domain partition generated by the set of boundaries, frequently considered when dealing with PWL functions. The realization method of lattice models is adapted to the three region configurations, comparing the efficiency of the resulting versions.     

A polynomial time upper bound for the number of contacts in the HP-model on the face-centered-cubic lattice (FCC)

Lattice protein models are a major tool for investigating principles of protein folding. For this purpose, one needs an algorithm that is guaranteed to find the minimal energy conformation in some lattice model (at least for some sequences). So far, there are only algorithm that can find optimal conformations in the cubic lattice. In the more interesting case of the face-centered-cubic lattice (FCC), which is more protein-like, there are no results. One of the reasons is that for finding optimal conformations, one usually applies a branch-and-bound technique, and there are no reasonable bounds known for the FCC. We will give such a bound for Dill's HP-model on the FCC, which can be calculated by a dynamic programming approach.     

Two-boundary lattice paths and parking functions

We describe an involution on a set of sequences associated with lattice paths with north or east steps constrained to lie between two arbitrary boundaries. This involution yields recursions (from which determinantal formulas can be derived) for the number and area enumerator of such paths. An analogous involution can be defined for parking functions with arbitrary lower and upper bounds. From this involution, we obtained determinantal formulas for the number and sum enumerator of such parking functions. For parking functions, there is an alternate combinatorial inclusion–exclusion approach. The recursions also yield Appell relations. In certain special cases, these Appell relations can be converted into rational or algebraic generating functions.     

环上的模糊理想幂格及其强截集诱导的格

给出了环上模糊理想幂格的概念,得到相关性质。进而由环上模糊理想强截集诱导出格,讨论了它不是分配格,但为模格。同时,将环上升为主理想环,得到了模糊理想乘积的强截集等于强截集的乘积,且都为环的理想。最后,讨论了Boolean环的模糊子集为模糊理想与其伴随构成交半格的关系。     

On the interior lattice points of convex lattice 11-gon

A lattice point in the plane is a point with integer coordinates. A lattice polygon K is a polygon whose vertices are lattice points. In this note we prove that any convex lattice 11-gon contains at least 15 interior lattice points.