Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

Voronoi diagram and medial axis algorithm for planar domains with curved boundaries — II: Detailed algorithm description

Details of algorithms to construct the Voronoi diagrams and medial axes of planars domain bounded by free-form (polynomial or rational) curve segments are presented, based on theoretical foundations given in the first installment Ramamurthy and Farouki, J. Comput. Appl. Math. (1999) 102 119–141 of this two-part paper. In particular, we focus on key topological and computational issues that arise in these constructions. The topological issues include: (i) the data structures needed to represent various geometrical entities — bisectors, Voronoi regions, etc., and (ii) the Boolean operations (i.e., union, intersection, and difference) on planar sets required by the algorithm. Specifically, representations for the Voronoi polygons of boundary segments, and for individual Voronoi diagram or medial axis edges, are proposed. Since these edges may be segments of (a) nonrational algebraic curves (curve/curve bisectors); (b) rational curves (point/curve bisectors); or (c) straight lines (point/point bisectors), data structures tailored to each of these geometrical entities are introduced. The computational issues addressed include the curve intersection algorithms required in the Boolean operations, and iterative schemes used to precisely locate bifurcation or “n-prong” points (n ⩾ 3) of the Voronoi diagram and medial axis. A selection of computed Voronoi diagram and medial axis examples is included to illustrate the capabilities of the algorithm.     

A Boolean matrix iteration in timetable construction

The annoying experience in timetable construction is that usually a complete timetable cannot be found without violating or diminishing some preconditions, even if the problem is theoretically solvable. Neither the control of the Hall conditions by Gotlieb's process of reducing availabilities nor the application of elaborate exchange operations guarantees a solution. In this paper an iteration of elementary implications is described which is expected to improve this situation, if applied in the final period of construction. In the course of these investigations, some formulas on Boolean matrices are derived, and a Galois connection between sets of Boolean vectors and Boolean matrices is exhibited.     

Spline R-Function and Applications in FEM

R-function is a widely used tool when considering objects obtained through the Boolean operations start from simple base primitives. However, there is square root operation in the representation. Considering that the use of splines will facilitate the calculations within the CAD system, in this paper, we propose a system of R-functions represented in spline form called Spline R-function (SR). After transforming the function ranges of two base primitives to a new coordinate system, a series of sign constraints following a specific Boolean operation are derived and the spline R-function can be formulated as a piecewise function. Representation of SR in both Bézier form and B-spline form have been given. Among which the Bézier ordinates are determined with the help of the B-net method through setting up a series of relations according to the sign constraints and properties of R-functions. The construction processes for both Boolean intersection and union operations with different smoothness are discussed in detail. Numerical experiments are conducted to show the potential of the proposed spline R-function.     

Fuzzy prime Boolean filters and their operations in IMT L-algebras

Some characterizations of fuzzy prime Boolean filters of IMT L-algebras are given. The lattice operations and the order-reversing involution on the set PB(M) of all fuzzy prime Boolean filters of IMT L-algebras are defined. It is showed that the set PB(M) endowed with these operations is a complete quasi-Boolean algebra (a distributive complete lattice with an order-reversing involution). It is derived that the algebra M=F, which is the set of all cosets of F, is isomorphic to the Boolean algebra {0; 1} if F is a fuzzy prime Boolean filter. By introducing an adjoint pair on PB(M), it is proved that the set PB(M) is also a residuated lattice.     

Borderline vs. unknown: comparing three-valued representations of imperfect information

In this paper we compare the expressive power of elementary representation formats for vague, incomplete or conflicting information. These include Boolean valuation pairs introduced by Lawry and González-Rodríguez, orthopairs of sets of variables, Boolean possibility and necessity measures, three-valued valuations, supervaluations. We make explicit their connections with strong Kleene logic and with Belnap logic of conflicting information. The formal similarities between 3-valued approaches to vagueness and formalisms that handle incomplete information often lead to a confusion between degrees of truth and degrees of uncertainty. Yet there are important differences that appear at the interpretive level: while truth-functional logics of vagueness are accepted by a part of the scientific community (even if questioned by supervaluationists), the truth-functionality assumption of three-valued calculi for handling incomplete information looks questionable, compared to the non-truth-functional approaches based on Boolean possibility–necessity pairs. This paper aims to clarify the similarities and differences between the two situations. We also study to what extent operations for comparing and merging information items in the form of orthopairs can be expressed by means of operations on valuation pairs, three-valued valuations and underlying possibility distributions.     

Characterization of binary polynomials of idempotent algebras

In this paper, we characterize the set of all binary algebraic (or polynomial) operations of an idempotent algebra that has at least one r-ary algebraic operation, (r ≥ 2), depending on every variable such that there is no an (r+2)-ary algebraic operation depending on at least (r+1) variables. We prove that this set forms a finite Boolean algebra, and then we characterize this Boolean algebra.     

Hyperarithmetical Boolean Algebras with a Distinguished Ideal

We prove a general theorem that allows us to pass from a hyperarithmetical Boolean algebra with a distinguished ideal to some computable Boolean algebra connected with the former by natural algebraic operations. Some examples are given.     

Interpolation and the Robinson property for logics not closed under the Boolean operations

A variant of the Robinson property (ROB^*) is introduced. The property ROB^* is equivalent to the usual Robinson property and hence is equivalent also to the interpolation property, in any compact logic closed under the Boolean operations. On the other hand, it will be shown that ROB^* is not always equal to the interpolation property, if a logic is not closed under them. Next, we will study ROB^* and various interpolation properties for equational logics, which are typical examples of compact logics not closed under the Boolean operations. It will be shown that an equational logic has ROB^* if and only if it has the amalgamation property for isomorphic embeddings.Presented by Bjarni Jonsson.     

The structure of separable Dynkin algebras

Abstract Dynkin algebras are studied. Such algebras form a useful instrument for discussing probabilities in a rather natural context. Abstractness means the absence of a set-theoretic structure of elements in such algebras. A large useful class of abstract algebras, separable Dynkin algebras, is introduced, and the simplest example of a nonseparable algebra is given. Separability allows us to define appropriate variants of Boolean versions of the intersection and union operations on elements. In general, such operations are defined only partially. Some properties of separable algebras are proved and used to obtain the standard intersection and union properties, including associativity and distributivity, in the case where the corresponding operations are applicable. The established facts make it possible to define Boolean subalgebras in a separable Dynkin algebra and check the coincidence of the introduced version of the definition with the usual one. Finally, the main result about the structure of separable Dynkin algebras is formulated and proved: such algebras are represented as set-theoretic unions of maximal Boolean subalgebras. After preliminary preparation, the proof reduces to the application of Zorn’s lemma by the standard scheme.     

Models of stochastic geometry — A survey

This paper discusses some models of stochastic geometry which are of potential interest for operations research. These are the Boolean model, a certain model for random compact sets and marked point processes. The Boolean model is a generalization of the well-known queueing systemM/G/. The random compact set model may be useful for modelling spatial spreading processes such as fires, cancers or holes in the Earth's surface. Marked point processes are used here as models of forests and used for a statistical study of the spatial distribution of damaged trees.Extended version of an Invited Lecture on the 16th Symposium for OR in Hamburg 1992.     

Equivalence of operations with respect to discriminator clones

For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of the other using operations from C. In this paper we prove that if C is a discriminator clone on a finite set, then there are only finitely many C-equivalence classes. Moreover, we show that the smallest discriminator clone is minimal with respect to this finiteness property. For discriminator clones of Boolean functions we explicitly describe the associated equivalence relations.     

线面体布尔运算的模糊逻辑方法

本文推广第二作者建立色觉机制数学模型时发明的一种连续值逻辑方法－模糊开关准布尔代数，得到了线面体混合布尔函数－若干个互不相交的子区域－边界的求解方法；这种方法用布尔代数公式和ｍａｘ、ｍｉｎ运算代替复杂的条件判断，具有可靠性、通用性和简洁性。     

Moving Out the Edges of a Lattice Polygon

We review previous work of (mainly) Koelman, Haase and Schicho, and Poonen and Rodriguez-Villegas on the dual operations of (i) taking the interior hull and (ii) moving out the edges of a two-dimensional lattice polygon. We show how the latter operation naturally gives rise to an algorithm for enumerating lattice polygons by their genus. We then report on an implementation of this algorithm, by means of which we produce the list of all lattice polygons (up to equivalence) whose genus is contained in {1,…,30}. In particular, we obtain the number of inequivalent lattice polygons for each of these genera. As a byproduct, we prove that the minimal possible genus for a lattice 15-gon is 45.     

交互式点云建模系统

设计和实现了一个用于车载激光扫描点云处理的交互式建模系统.其原理是:在真实建筑物激光扫描数据的基础上,通过RANSAC实现自动化点云几何特征提取预处理,采用交互引导的方式辅助特征提取,采用随机算法计算边界特征,并通过构建多边形边界邻接图,计算建筑物几何模型.除特征提取外,涉及到的计算都是实时的.与传统处理方法相比,该系统具有速度快、精度高等优点.     

布尔矩阵的可实现问题及其与色数问题的关系

讨论了布尔矩阵的可实现问题及其与色数问题的关系.首先给出布尔矩阵可实现的一些充要条件,讨论可实现布尔矩阵的性质,其次证明可实现布尔矩阵的容度等于该矩阵所生成的图的色数;简单图的邻接矩阵的对偶阵是可实现的,且其容度就是简单图的色数的一个上界.     

BOOLEAN ALGEBRAS IN AST

In this paper we investigate Boolean algebras and their subalgebras in Alternative Set Theory (AST). We show that any two countable atomless Boolean algebras are isomorphic and we give an example of such a Boolean algebra. One other main result is, that there is an infinite Boolean algebra freely generated by a set. At the end of the paper we show that the sentence “There is no non-trivial free group which is a set” is consistent with AST.     

SECOND-ORDER BOOLEAN ALGEBRAS

Opgedra aan Prof. Hennie Schutte by geleentheid van sy sestigste verjaarsdag.

Abstract

A Boolean algebra is the algebraic version of a field of sets. The complex algebra C(B) of a Boolean algebra B is defined over the power set of B; it is a field of sets with extra operations. The notion of a second-order Boolean algebra is intended to be the algebraic version of the complex algebra of a Boolean algebra. To this end a representation theorem is proved.     

On convexification of polygons by pops

Given a polygon P in the plane, a pop operation is the reflection of a vertex with respect to the line through its adjacent vertices. We define a family of alternating polygons, and show that any polygon from this family cannot be convexified by pop operations. This family contains simple as well as non-simple (i.e., self-intersecting) polygons, as desired. We thereby answer in the negative an open problem posed by Demaine and O’Rourke (2007) [9, Open Problem 5.3].     

Computational aspects of Boolean cubature

Boolean methods of interpolation [1,4] have been applied to construct multivariate quadrature rules for periodic functions of Korobov classes which are comparable with lattice rules of numerical integration [6,7]. In particular, we introducedd-variate Boolean trapezoidal rules [3,4] andd-variate Boolean midpoint rules [2,4]. The basic tools for constructing Boolean midpoint rules are Boolean midpoint sums. It is the purpose of this paper to use a modification of these Boolean midpoint sums to compute Boolean trapezoidal rules in an efficient way.