Secure Two-Party Computational Geometry

Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric. problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.

Weight-based shape modification of NURBS curves by constrained optimization

A new method for shape modification of non-uniform rational B-splines (NURBS) curves was presented, which was based on constrained optimization by means of altering the corresponding weights of their control points. Using this method, the original NURBS curve was modified to satisfy the specified geometric constraints, including single point and multi-point constraints. With the introduction of free parameters, the shapes of modified NURBS curves could be further controlled by users without destroying geometric constraints and seem more naturally. Since explicit formulae were derived to compute new weights of the modified curve, the method was simple and easy to program. Practical examples showed that the method was applicable for computer aided design (CAD) system.

APPROXIMATE QUERY AND CALCULATION OF RNN_k BASED ON VORONOI CELL

Reverse k nearest neighbor （RNNk） is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data points which use a query point as one of their k nearest neighbors. To answer the RNNk of queries efficiently, the properties of the Voronoi cell and the space-dividing regions are applied. The RNNk of the given point can be found without computing its nearest neighbors every time by using the rank Voronoi cell. With the elementary RNNk query result, the candidate data points of reverse nearest neighbors can he further limited by the approximation with sweepline and the partial extension of query region Q. The approximate minimum average distance （AMAD） can be calculated by the approximate RNNk without the restriction of k. Experimental results indicate the efficiency and the effectiveness of the algorithm and the approximate method in three varied data distribution spaces. The approximate query and the calculation method with the high precision and the accurate recall are obtained by filtrating data and pruning the search space.

IMPROVEMENTS IN HIDDEN LINE REMOVAL ALGORITHM FOR BI-PARAMETRIC SURFACES

A hidden line removal algorithm for bi parametric surfaces is presented and illustrated by some experimental results. The enclosure test is done using area coordinates. A technique of moving box of encirclement is presented. It is found that the algorithm is of general purpose, requires minimal computer storage, has high accuracy and simplicity, and is very easy to be implemented on a computer.

A new algorithm for computing the convex hull of a planar point set

When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.

Characteristic Polynomial Assignment in 2-D System

The closed loop polynomial assignment problems of 2D systems Roesser model with multiple inputs were studied. The problems were transferred to a rational map and were assigned a sate feedback and output feedback. Sufficient conditions for the system were derived using the algebraic geometric methods.

The Ellipsoidal Invariant Set of Fractional Order Systems Subject to Actuator Saturation:The Convex Combination Form

The domain of attraction of a class of fractional order systems subject to saturating actuators is investigated in this paper. We show the domain of attraction is the convex hull of a set of ellipsoids. In this paper, the Lyapunov direct approach and fractional order inequality are applied to estimating the domain of attraction for fractional order systems subject to actuator saturation. We demonstrate that the convex hull of ellipsoids can be made invariant for saturating actuators if each ellipsoid with a bounded control of the saturating actuators is invariant. The estimation on the contractively invariant ellipsoid and construction of the continuous feedback law are derived in terms of linear matrix inequalities (LMIs). Two numerical examples illustrate the effectiveness of the developed method. © 2014 Chinese Association of Automation.

Some Properties of the Sum and Geometric Differences of Minkowski

The sets of Minkowski algebraic sum and geometric difference are considered. The purpose of the research in this paper is to apply the properties of Minkowski sum and geometric difference to fractional differential games. This paper investigates the geometric properties of the Minkowski algebraic sum and the geometric difference of sets. Various examples are considered that calculate the geometric differences of sets. The results of the research are presented and proved as a theorem. At the end of the article, the results were applied to fractional differential games.

A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram

Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

Secure planar convex hull protocol for large-scaled point sets in semi-honest model

Efficiency and scalability are still the bottleneck for secure multi-party computation geometry （SMCG）. In this work a secure planar convex hull （SPCH） protocol for large-scaled point sets in semi-honest model has been proposed efficiently to solve the above problems. Firstly, a novel priva- cy-preserving point-inclusion （PPPI） protocol is designed based on the classic homomorphic encryp- tion and secure cross product protocol, and it is demonstrated that the complexity of PPPI protocol is independent of the vertex size of the input convex hull. And then on the basis of the novel PPPI pro- tocol, an effective SPCH protocol is presented. Analysis shows that this SPCH protocol has a good performance for large-scaled point sets compared with previous solutions. Moreover, analysis finds that the complexity of our SPCH protocol relies on the size of the points on the outermost layer of the input point sets only.

3D Surface Editing Based on Level-Sets

A novel method which integrates the topological flexibility of the level-set approach and the simplicity of point-sampled surfaces is proposed. The grid structure resulted from the level-set approach not only offers a wide range of powerful surface editing techniques for the point set surface editing, but also facilitates the topological change with ease. With the aid of point-based resampling, the method updates the surface shape of the point-based geometry quickly without worrying about point connectivity at all. The point set surface can also change its topology properly whenever a collision with other parts of itself is detected. The experiment demonstrates their effectiveness on several scanned objects and scan-converted models. Four examples of surface editing operations： smoothing, tapering, deforming, and Boolean operations, are presented.

Slicing Strategy for Selective Laser Melting

Selective laser melting （SLM） is one of the most popular additive manufacturing （AM） technologies for metal parts. Slicing result, especially for the different dimensional slicing geometry and its topology, plays an important role because of the thermodynamic behavior of metal powders. To get correct geometry and reliable topology, a slicing strategy for SLM is proposed. The unavoidable numerical error caused by sampling and geometric transformation is suppressed firstly, according to shifting the z-coordinate of a vertex with a small value such the shifted vertex is on a slicing plane. The result of vertex-shifting makes it possible to identify different geometric features such as skin surfaces, overhang surfaces, extreme edges and volumetric solid. Second, from geometric primitives a hierarchy of axis-aligned bounding boxes （AABBs） is constructed and used to speed up intersection of slicing planes against sets of triangles. All intersecting segments are given different signs to depict their geometric or topological information. Based the different signs, the different dimensional geometry that is eventually represented by simple and anticlockwise oriented polygons, are identified. Finally, the polygons are classified and nested in a multi-tree data structure set to produce correct topological relations. The result of digital and physical experiments shows the proposed slicing strategy is feasible and robust.

3D Modelling of Biological Systems for Biomimetics

With the advanced development of computer-based enabling technologies, many engineering, medical, biology, chemistry, physics and food science etc have developed to the unprecedented levels, which lead to many research and development interests in various multi-discipline areas. Among them, biomimetics is one of the most promising and attractive branches of study. Biomimetics is a branch of study that uses biological systems as a model to develop synthetic systems. To learn from nature, one of the fundamental issues is to understand the natural systems such animals, insects, plants and human beings etc. The geometrical characterization and representation of natural systems is an important fundamental work for biomimetics research. 3D modeling plays a key role in the geometrical characterization and representation, especially in computer graphical visualization. This paper firstly presents the typical procedure of 3D modelling methods and then reviews the previous work of 3D geometrical modelling techniques and systems developed for industrial, medical and animation applications. Especially the paper discusses the problems associated with the existing techniques and systems when they are applied to 3D modelling of biological systems. Based upon the discussions, the paper proposes some areas of research interests in 3D modelling of biological systems and for Biomimetics.

Secure Two-Party Point-Circle Inclusion Problem

Privacy-preserving computational geometry is a special secure multi-party computation and has many applications. Previous protocols for determining whether a point is inside a circle are not secure enough. We present a two-round protocol for computing the distance between two private points and develop a more efficient protocol for the point-circle inclusion problem based on the distance protocol. In comparison with previous solutions, our protocol not only is more secure but also reduces the number of communication rounds and the number of modular multiplications significantly.

Method to improve the performance of reflectance diffuse optical imaging based on polygonal optical fibers arrangement

In order to improve the performance of reflectance diffuse optical imaging （rDOI）, a novel polynomial geometry （PG） of optical fibers arrangement is proposed. Polynomial geometry is based on the hexagonal geometry （HG） and multicentered double-density （MD） mode. The overlapping sensitivity matrix, area ratio （AR）, reconstruction image, two-absorber model, and contrast-to-noise ratio （CNR） in different depths are used to evaluate the performance of PG. The other three geometries including HG, rectangular geometry （RG）, and MD mode are also compared with PG. The deformation of the reconstruction images is evaluted by circular ratio （CR）. The results prove that the proposed PG has high performance and minimum deformation in quality of reconstruction image in rDOI.

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.

Contact theory and algorithm

In discontinuous computations,contacts between two general blocks A and B are common and represent a fundamental problem.This paper presents a mathematically proven theory and algorithm to address this problem.In the proposed approach,a reference point a0 is selected from block A,and the contacts between blocks A and B are transferred to the contact of the reference point a0 and the entrance block E(A,B).Discontinuity related computations DEM,DDA,and FEM can use this mathematically proven theory and algorithm directly.

Searching a Polygonal Region by Two Guards

We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O（n） time algorithm to determine the two-guard searchability in a polygon, and an O（n log n ＋ m） time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m （≤ n^2） is the number of search instructions reported.

Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.

Structurally coupled characteristics of rotor blade geometrically exact formulation

In rotor dynamics,blades are normally modelled as a slender beam,in which elastic deformations are coupled with each other.To identify these coupling effects,new rigid-flexible structural model for helicopter rotor system is proposed in this paper.Finite rotations of the whole blade(on flapwise,lagwise,and torsional)are described as three global rigid degrees of freedom.The nonlinear deformation geometrics of the beam is built on geometrically exact beam theory.New expressions for blade strain energy,kinetic energy,and virtual work of various kinds of external forces are derived as functions of finite rotations and elastic deformations.To quantify the coupling characteristics,following the definition of coupling factor in electromagnetics,a new coupling factor between two modal components on each mode is introduced in modal analysis.Simulations show that the new structural model is highly capable of solving static and dynamic problems in rotor system and the maximum deformation that moderate deformation beam theory can predict might be 15%of beam length.After the new coupling factor is applied to study structurally coupled characteristics of rotor blade,it can be concluded that closeness of natural frequencies likely indicates considerable coupling between corresponding DOFs in structure.