Binary Plane Partitions for Disjoint Line Segments

A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition where each step partitions the space (and possibly some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open half-spaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of n disjoint line segments in the plane admits a BSP of size O(nlog n/log log n). This bound is the best possible.     

一种高效快速的裁剪算法

本文的裁剪策略是，巧妙的利用窗口与线段的两种不同数学描述，将有效交点的判定、求交运算及包含性检验，归结为三个条件的判别。     

The volume of simplices clipped by a half space

Formulas for the volume of n-simplices clipped by a half space in Rⁿ are given in terms of the values of a function at the vertices of the simplices.     

Semiparametric variable selection for partially varying coefficient models with endogenous variables

By using instrumental variable technology and the partial group smoothly clipped absolute deviation penalty method, we propose a variable selection procedure for a class of partially varying coefficient models with endogenous variables. The proposed variable selection method can eliminate the influence of the endogenous variables. With appropriate selection of the tuning parameters, we establish the oracle property of this variable selection procedure. A simulation study is undertaken to assess the finite sample performance of the proposed variable selection procedure.     

高维线性回归模型中非凸惩罚岭回归

非凸惩罚函数包括SCAD惩罚和MCP惩罚, 这类惩罚函数具有无偏性、连续性和稀疏性等特点,岭回归方法能够很好的克服共线性问题. 本文将非凸惩罚函数和岭回归方法的优势结合起来(简记为 NPR),研究了自变量间存在高相关性问题时NPR估计的Oracle性质. 这里主要研究了参数个数$p_n$ 随样本量$n$ 呈指数阶增长的情况. 同时, 通过模拟研究和实例分析进一步验证了NPR 方法的表现.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

Splitting Operation and Connectedness in Binary Matroids

In [3], the authors have extended the splitting operation of graphs to binary matroids. In this paper we explore the relationship between the splitting operation and connectedness in binary matroids. We prove that repeated applications of splitting operation on a bridgeless disconnected binary matroid leads to a connected binary matroid. We extend splitting lemma of graphs [1] to binary matroids.     

Binary formally self-dual odd codes

Most of the research on formally self-dual (f.s.d.) codes has been developed for binary f.s.d. even codes, but only limited research has been done for binary f.s.d. odd codes. In this article we complete the classification of binary f.s.d. odd codes of lengths up to 14. We also classify optimal binary f.s.d. odd codes of length 18 and 24, so our result completes the classification of binary optimal f.s.d. odd codes of lengths up to 26. For this classification we first find a relation between binary f.s.d. odd codes and binary f.s.d. even codes, and then we use this relation and the known classification results on binary f.s.d. even codes. We also classify (possibly) optimal binary double circulant f.s.d. odd codes of lengths up to 40.     

Cyclic regulating balanced Butler groups

A necessary and sufficient condition is derived for an arbitrary cyclic regulating almost completely decomposable group to belong to a K(n)-class, n≥ 0. This allows one to formulate a Structure Theorem for clipped p-primary cyclic regulating groups in each K(n)-class. Using the Indecomposability Criterion we construct an example of an indecomposable balanced Butler group which does not have a unique regulating subgroup. Received: 3 November 1998     

Nilpotency of the Alternator Ideal of a Finitely Generated Binary (-1,1)-Algebra

We prove nilpotency of the alternator ideal of a finitely generated binary (-1,1)-algebra. An algebra is a binary (-1,1)-algebra if its every 2-generated subalgebra is an algebra of type (-1,1). While proving the main theorem we obtain various consequences: a prime finitely generated binary (-1,1)-algebra is alternative; the Mikheev radical of an arbitrary binary (-1,1)-algebra coincides with the locally nilpotent radical; a simple binary (-1,1)-algebra is alternative; the radical of a free finitely generated binary (-1,1)-algebra is solvable. Moreover, from the main result we derive nilpotency of the radical of a finitely generated binary (-1,1)-algebra with an essential identity.     

On the linear complexity of binary lattices

Linear complexity is an important and frequently used measure of unpredictability and pseudorandomness of binary sequences. In this paper our goal is to extend this notion to two dimensions. We will define and study the linear complexity of binary lattices. The linear complexity of a truly random binary lattice will be estimated. Finally, we will analyze the connection between linear complexity and correlation measures, and we will utilize the inequalities obtained in this way for estimating the linear complexity of an important special binary lattice. Finally, we will study the connection between the linear complexity of binary lattices and of the associated binary sequences.     

Ideals and the binary discriminator in universal algebra

We introduce the binary discriminator and the dual binary discriminator and the corresponding universal algebras with 0. The latter are related to permutability and distributivity at 0. For A finite the dual binary discriminator is in the intersection of all maximal subclones of the clone of all f satisfying f (0,...,0) = 0 (except certain maximal subclones if A is of prime power cardinality). An algebra with a special binary term function and a special unary term function is a dual binary discriminator algebra if and only if it is ideal-free. Finally we characterize binary and dual binary discriminator varieties. Received April 3, 1997; accepted in final form July 28, 1998.     

Modeling disjunctive constraints with a logarithmic number of binary variables and constraints

Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of a finite number of specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints linear in the number of polyhedra. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints logarithmic in the number of polyhedra. Using these conditions we introduce mixed integer binary formulations for SOS1 and SOS2 constraints that have a number of binary variables and extra constraints logarithmic in the number of continuous variables. We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations.     

Fixed-bucket binary storage trees

A binary storage tree has a set or bucket of possible items associated with each node. The buckets at deeper levels are refinements of the partitionings at earlier levels. When these buckets are established a priori, rather than determined by the particular items stored, we obtain a storage data structure which is a generalized binary digital tree as well as a binary storage tree. Thus the binary key-values of the items along a path in a fixed-bucket binary storage tree have successively longer common prefixes. This synthesis of two schemes inherits all the desirable properties of both methods. The method is analyzed for uniformly-distributed input and shown to have the same cost statistics as binary digital trees.     

On Binary Resilient Functions

Using a lifting formula for the coefficients of Boolean functions, we characterize binary resilient functions as binary matrices with certain row or column intersection properties. We give some new constructions of binary resilient functions based on this characterization. In particular, we show that the incidence matrix of a Steiner system can be used to construct binary resilient functions.     

二值形态运算的感知器模型及其应用

给出了二值形态运算模型与感知器模型之间的关系.以此为基础对传统的二值数学形态学基本运算进行了推广,建立了基于感知器的形态运算模型.新的模型为传统的二值形态运算赋予了可调节机制.计算机模拟实验表明该方法较传统的二值形态运算有效.     

Bridge estimation for generalized linear models with a diverging number of parameters

Variable selection is fundamental to high dimensional generalized linear models. A number of variable selection approaches have been proposed in the literature. This paper considers the problem of variable selection and estimation in generalized linear models via a bridge penalty in the situation where the number of parameters diverges with the sample size. Under reasonable conditions the consistency of the bridge estimator can be achieved. Furthermore, it can select the nonzero coefficients with a probability converging to 1 and the estimators of nonzero coefficients have the asymptotic normality, namely the oracle property. Our simulations indicate that the bridge penalty is an effective consistent model selection technique and is comparable to the smoothly clipped absolute deviation procedure. A real example analysis is presented.     

A unified theory for coherent systems in reliability part III: Two special cases for multinary systems—binary-type coherence and homogeneous coherence

As shown in a companion-paper,¹ binary and multinary coherent systems can be studied with unified arguments, through monotone binary coherent systems. These are binary coherent systems submitted to some monotone constraint and generalize the classic theory of free binary coherent systems. By considering the unified point of view thus obtained, this paper gives what is perhaps the most suggestive representation for multinary coherent systems, since this extends the definition of binary coherent systems in terms of series-parallel (parallel-series) structures. Then, this paper examines the special case of multinary systems that can be studied directly with the classic theory of free binary coherent systems. It thus enlarges and complements, in a shorter unified manner, the particular cases considered in earlier studies.     

Binary extended formulations of polyhedral mixed-integer sets

We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.