A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k ³n) expected time and O(k²n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ^(d+1)/2+1 n ^(d+1)/2) and space complexityO(k ^(d+1)/2 n ^(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

Finding a minimal cover for binary images: An optimal parallel algorithm

Given a black-and-white image, represented by an array of n × n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.The research reported here forms part of the author's doctoral dissertion, submitted to Cornell University in May 1989. This work was partially supported by NSF Grant DC1-86-02256, IBM Agreement 12060043, and ONR Contract N00014-83-K-0640. A preliminary version of this paper was presented at the 26th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, September 28–30, 1988.     

A new approach to rectangle intersections part I

Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.     

基于表面及切向属性的点模型骨架提取方法

针对目前在离散点云模型以及低分辨率模型上提取骨架算法存在的局限性,提出一种基于表面及切向属性(attributesofsurfaceandtangency,AST)的新方法.首先给出两个属性定义及其计算方式.然后基于上述属性通过表面光滑收缩和骨架吸引的双重作用达到模型的几何收缩,连接迭代收缩完成后得到的中心点,从而得到模型的骨架.实验表明:该方法得到的骨架能较好地表达原始模型的几何特征和拓扑结构,在缺少连接信息和低分辨率的情况下也能获得较好的骨架提取效果.     

基于聚类分析与几何的目标特征敏感性评估算法

为克服在较少先验知识的情况下,人为选择目标特征进行分类识别的盲目性,提出一种基于聚类分析与几何学的目标特征评估方法.该方法在类内类间距离的基础上引入几何学中有关圆的知识,定义了样本在特征空间中分布的＂紧密度＂、＂分离度＂函数和＂松紧度＂权重,以考察目标特征对目标样本之间的分类敏感性,并根据评估结果选取适当特征构成一个新的联合特征,以提高对目标的分类识别效率.最后通过仿真验证了该方法的有效性.     

Interplay Between Wetting and Phase Behavior in Binary Polymer Films and Wedges: Monte Carlo Simulations and Mean Field Calculations

Confining a binary mixture, one can profoundly alter its miscibility behavior. The qualitative features of miscibility in confined geometry are ratheruniversal and shared by polymer mixtures as well as small molecules, but the unmixing transition in the bulk and the wetting transition are typically well separated in polymer blends. The interplay between wetting and miscibility of a symmetric polymer mixture via large-scale Monte Carlo simulations in the framework of the bond fluctuation model and via numerical self–consistent field calculations is studied. The film surfaces interact with the monomers via short ranged potentials, and the wetting transition of the semi–infinite system is of first order. It can be accurately located in the simulations by measuring the surface and interface tensions and using Young’s equation. If both surfaces in a film attract the same component, capillary condensation occurs and the critical point is close to the critical point of the bulk. If surfaces attract different components, an interface localization/delocalization occurs which gives rise to phase diagrams with two critical points in the vicinity of the pre-wetting critical point of the semi–infinite system. The crossover between these two types of phase diagrams as a function of the surface field asymmetry is studied. The dependence of the phase diagram on the film thickness Δ for antisymmetric surface fields is investigated. Upon decreasing the film thickness, the two critical points approach the symmetry axis of the phase diagram, and below a certain thickness Δ_tri, there remains only a single critical point at the symmetric composition. This corresponds to a second-order interface localization/delocalization transition even though the wetting transition is of first order. At a specific film thickness, Δ_tri, tricritical behavior is found. The behavior of antisymmetric films is compared with the phase behavior in an antisymmetric double wedge. While the former is the analog of the wetting transition of a planar surface, the latter is related to the filling behavior of a single wedge. Evidence for a second-order interface localization/delocalization transition in an antisymmetric double wedge is presented, and its unconventional critical behavior is related to the predictions of Parry et al. (Phys. Rev. Lett. 83:5535 (1999)) for wedge filling. The critical behavior differs from the Ising universality class and is characterized by strong anisotropic fluctuations.Invited paper presented at the Fifteenth Symposium on Thermophysical Properties, June 022–27, 2003, Boulder, Colorado, U.S.A.     

Optimal design of optical performance of reflective ferroelectric‐ and anti‐ferroelectric liquid‐crystal displays

Abstract— In an in‐plane optical geometry, such that the average optic axis lies on the plane parallel to both substrates, the optical properties of a reflective ferroelectric liquid‐crystal (FLC) or antiferroelectric liquid‐crystal (AFLC) cell were studied within the framework of the 2 × 2 Jones matrix formalism. To obtain good achromaticity and high brightness, the cell parameters such as the molecular rotation angle and the effective phase retardation of the AFLC layer were optimized. The device performances of the AFLC cell were experimentally demonstrated in this geometry.     

Computing the update of the repeated median regression line in linear time

The repeated median line estimator is a highly robust method for fitting a regression line to a set of n data points in the plane. In this paper, we consider the problem of updating the estimate after a point is removed from or added to the data set. This problem occurs, e.g., in statistical online monitoring, where the computational effort is often critical. We present a deterministic algorithm for the update working in O(n) time and O(n²) space.     

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.