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 c...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.展开更多
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. Suff...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 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 ga...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 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...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.展开更多
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 ...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.展开更多
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 researc...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.展开更多
We present a visual analysis environment based on a multi-scale partitioning of a 2d domain intoregions bounded by cycles in weighted planar embedded graphs.The work has been inspired by anapplication in granular mate...We present a visual analysis environment based on a multi-scale partitioning of a 2d domain intoregions bounded by cycles in weighted planar embedded graphs.The work has been inspired by anapplication in granular materials research,where the question of scale plays a fundamental role inthe analysis of material properties.We propose an efficient algorithm to extract the hierarchical cyclestructure using persistent homology.The core of the algorithm is a filtration on a dual graph exploitingAlexander’s duality.The resulting partitioning is the basis for the derivation of statistical properties thatcan be explored in a visual environment.We demonstrate the proposed pipeline on a few syntheticand one real-world dataset.展开更多
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 ...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.展开更多
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...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.展开更多
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...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.展开更多
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 ...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.展开更多
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 matt...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.展开更多
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 boun...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.展开更多
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 sy...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.展开更多
Despite the rapid development of quantum research in recent years,there is very little research in computational geometry.In this paper,to achieve the convex hull of a point set in a quantum system,a quantum convex hu...Despite the rapid development of quantum research in recent years,there is very little research in computational geometry.In this paper,to achieve the convex hull of a point set in a quantum system,a quantum convex hull algorithm based on the quantum maximum or minimum searching algorithm(QUSSMA)is proposed.Firstly,the novel enhanced quantum representation of digital images is employed to represent a group of point set,and then the QUSSMA algorithm and vector operation are used to search the convex hull of the point set.In addition,the algorithm is simulated and compared with the classical algorithm.It is concluded that the quantum algorithm accelerates the classical algorithm when the Mpvalue of the convex hull point is under a certain condition.展开更多
This paper explores the possibilities of very simple analysis on derivation of spiral regions for a single segment of cubic function matching positional,tangential,and curvature end conditions.Spirals are curves of mo...This paper explores the possibilities of very simple analysis on derivation of spiral regions for a single segment of cubic function matching positional,tangential,and curvature end conditions.Spirals are curves of monotone curvature with constant sign and have the potential advantage that the minimum and maximum curvature exists at their end points.Therefore,spirals are free from singularities,inflection points,and local curvature extrema.These properties make the study of spiral segments an interesting problem both in practical and aesthetic applications,like highway or railway designing or the path planning of non-holonomic mobile robots.Our main contribution is to simplify the procedure of existence methods while keeping it stable and providing flexile constraints for easy applications of spiral segments.展开更多
Point-based geometry representations have become widely used in numerous contexts,ranging from particle-based simulations,over stereo image matching,to depth sensing via light detection and ranging.Our application foc...Point-based geometry representations have become widely used in numerous contexts,ranging from particle-based simulations,over stereo image matching,to depth sensing via light detection and ranging.Our application focus is on the reconstruction of curved line structures in noisy 3D point cloud data.Respective algorithms operating on such point clouds often rely on the notion of a local neighborhood.Regarding the latter,our approach employs multi-scale neighborhoods,for which weighted covariance measures of local points are determined.Curved line structures are reconstructed via vector field tracing,using a bidirectional piecewise streamline integration.We also introduce an automatic selection of optimal starting points via multi-scale geometric measures.The pipeline development and choice of parameters was driven by an extensive,automated initial analysis process on over a million prototype test cases.The behavior of our approach is controlled by several parameters—the majority being set automatically,leaving only three to be controlled by a user.In an extensive,automated final evaluation,we cover over one hundred thousand parameter sets,including 3D test geometries with varying curvature,sharp corners,intersections,data holes,and systematically applied varying types of noise.Further,we analyzed different choices for the point of reference in the co-variance computation;using a weighted mean performed best in most cases.In addition,we compared our method to current,publicly available line reconstruction frameworks.Up to thirty times faster execution times were achieved in some cases,at comparable error measures.Finally,we also demonstrate an exemplary application on four real-world 3D light detection and ranging datasets,extracting power line cables.展开更多
In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties...In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.展开更多
The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm ...The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.展开更多
The maximum diameter color-spanning set problem(MaxDCS) is defined as follows: given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. I...The maximum diameter color-spanning set problem(MaxDCS) is defined as follows: given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O(n log n) time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem(AFFN) in the plane, and propose algorithms to answer the farthest foreign neighbor query(FFNQ) of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set(CPCS) in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.展开更多
文摘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.
文摘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 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 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.
基金Supported by Key Programs of the Chinese Academy of Sciences(No.KGZD-EW-T0)Research Fund for Scientific and Technological Projects of Chongqing(No.2012gg B40003 and cstc2013yykf C00006)
文摘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.
文摘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.
基金the Wallenberg AI,Autonomous Systems and Software Program(WASP)funded by the Knut and Alice Wallenberg Foundation,the SeRC(Swedish e-Science Research Center)and the ELLIIT environment for strategic research in Sweden,the Swedish Research Council(VR)grant 2019–05487an Indo-Swedish joint network project:DST/INT/SWD/VR/P-02/2019 VR grant 2018–07085.
文摘We present a visual analysis environment based on a multi-scale partitioning of a 2d domain intoregions bounded by cycles in weighted planar embedded graphs.The work has been inspired by anapplication in granular materials research,where the question of scale plays a fundamental role inthe analysis of material properties.We propose an efficient algorithm to extract the hierarchical cyclestructure using persistent homology.The core of the algorithm is a filtration on a dual graph exploitingAlexander’s duality.The resulting partitioning is the basis for the derivation of statistical properties thatcan be explored in a visual environment.We demonstrate the proposed pipeline on a few syntheticand one real-world dataset.
基金Supported by the National Natural Science Foundation of China (Grant No. 60573171), the National Grand Fundaznental Research 973 Program of China, (Grant No. 2006CB303006),and Research Program of Anhui Province Education Department (Grant Nos.2006KJ024A and JYXM2005166). We are very grateful to Professor X. Yao at University of Birmingham for useful comments and some corrections. We also thank Professor H. Shen at Japhan Advanced Institute of Science and Technology for helpful suggestions.
文摘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.
基金supported by the National Natural Science Foundation of China(No.30671997)the National "863" Program of China(No.2008AA02Z438).
文摘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.
基金This work is partially supported by Utah State University under Grant No.A13501.
文摘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.
基金This work was supported by the Key Research Program of Frontier Sciences CAS(Grant No.QYZDY-SSW-SYS004).
文摘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.
基金supported by the Grand-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan, and a research grant from Tokai University.
文摘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.
文摘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.
文摘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.
基金supported by the Shanghai Science and Technology Project in 2020 under Grant No.20040501500。
文摘Despite the rapid development of quantum research in recent years,there is very little research in computational geometry.In this paper,to achieve the convex hull of a point set in a quantum system,a quantum convex hull algorithm based on the quantum maximum or minimum searching algorithm(QUSSMA)is proposed.Firstly,the novel enhanced quantum representation of digital images is employed to represent a group of point set,and then the QUSSMA algorithm and vector operation are used to search the convex hull of the point set.In addition,the algorithm is simulated and compared with the classical algorithm.It is concluded that the quantum algorithm accelerates the classical algorithm when the Mpvalue of the convex hull point is under a certain condition.
文摘This paper explores the possibilities of very simple analysis on derivation of spiral regions for a single segment of cubic function matching positional,tangential,and curvature end conditions.Spirals are curves of monotone curvature with constant sign and have the potential advantage that the minimum and maximum curvature exists at their end points.Therefore,spirals are free from singularities,inflection points,and local curvature extrema.These properties make the study of spiral segments an interesting problem both in practical and aesthetic applications,like highway or railway designing or the path planning of non-holonomic mobile robots.Our main contribution is to simplify the procedure of existence methods while keeping it stable and providing flexile constraints for easy applications of spiral segments.
基金This research was funded through the Vice Rectorate of Research of the University of Innsbruck within the scope of the doctoral program Computational Interdisciplinary Modelling(DK CIM).
文摘Point-based geometry representations have become widely used in numerous contexts,ranging from particle-based simulations,over stereo image matching,to depth sensing via light detection and ranging.Our application focus is on the reconstruction of curved line structures in noisy 3D point cloud data.Respective algorithms operating on such point clouds often rely on the notion of a local neighborhood.Regarding the latter,our approach employs multi-scale neighborhoods,for which weighted covariance measures of local points are determined.Curved line structures are reconstructed via vector field tracing,using a bidirectional piecewise streamline integration.We also introduce an automatic selection of optimal starting points via multi-scale geometric measures.The pipeline development and choice of parameters was driven by an extensive,automated initial analysis process on over a million prototype test cases.The behavior of our approach is controlled by several parameters—the majority being set automatically,leaving only three to be controlled by a user.In an extensive,automated final evaluation,we cover over one hundred thousand parameter sets,including 3D test geometries with varying curvature,sharp corners,intersections,data holes,and systematically applied varying types of noise.Further,we analyzed different choices for the point of reference in the co-variance computation;using a weighted mean performed best in most cases.In addition,we compared our method to current,publicly available line reconstruction frameworks.Up to thirty times faster execution times were achieved in some cases,at comparable error measures.Finally,we also demonstrate an exemplary application on four real-world 3D light detection and ranging datasets,extracting power line cables.
文摘In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.
文摘The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.
基金supported by the International Science and Technology Cooperation Program of China under Grant No.2010DFA92720the National Natural Science Foundation of China under Grant Nos.11271351,60928006,and 61379087
文摘The maximum diameter color-spanning set problem(MaxDCS) is defined as follows: given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O(n log n) time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem(AFFN) in the plane, and propose algorithms to answer the farthest foreign neighbor query(FFNQ) of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set(CPCS) in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.