Search

Incremental algorithms are among the most popular approaches for Delaunay triangulation, and the point insertion sequence has a substantial impact on the amount of work needed to construct Delaunay triangulations in incremental algorithm triangulation. In this paper, 2D adaptive Hilbert curve insertion, including the method of dividing 3D multi-grids and adjusting the 3D adaptive Hilbert curve to avoid the "jump" phenomenon, is extended to 3D Delaunay triangulation. In addition, on the basis of adaptive Hilbert curve insertion, we continue to optimize the addition of control points by selecting control points in every order and every grid level. As a result, the number of conflicting elongated tetrahedra that have to be created and deleted multiple times and the number of search steps for positioning inserted points can both be reduced. Lastly, a new comparison method is used in the point location process to solve the precision problem in 3D Delaunay triangulation. As shown by detailed experiments and analysis, compared with previous adaptive Hilbert curve insertion, CGAL, regular grid insertion, multi-grid insertion and random insertion, the proposed 3D Delaunay triangulation is the most efficient for both artificial and real surface sampling point sets. [ABSTRACT FROM AUTHOR]

In provincial areas, allocation of the HV/MV substations aims to assign a proper set of numbers and locations of substations to supply loads spatially distributed over a large geographic area with continually emerging towns. This requires identifying the sparse load centers, the existing substations, and the new substations required to cover the potential extension. This paper proposes a method to allocate the main substations to the targeted area based on the lines' length which are assigned by Delaunay triangulation and geographical coordinates. The proposed configuration is identified by a criterion that is tailored to the Iraqi sub-transmission system in which the standard distances among the substation follow specific patterns. The standard distances that are identified by the proposed methods are represented by the edges of Delaunay triangles. This paper aims to improve the voltage regulation of the distribution grid and avoid problems of overloaded feeders by assigning the proposed locations that reduce the lines' lengths. The proposed method is verified using simulation tests on Diyala 9-bus system which is a part of the Iraqi 132 kV power system. The results show that the proposed configuration of the substations is reasonably valid and quite close to the real locations of the towns of the system with efficient lengths for the lines. [ABSTRACT FROM AUTHOR]

This paper describes a numerically robust data structure for encoding intrinsic triangulations of polyhedral surfaces. Many applications demand a correspondence between the intrinsic triangulation and the input surface, but existing data structures either rely on floating point values to encode correspondence, or do not support remeshing operations beyond basic edge flips. We instead provide an integer-based data structure that guarantees valid correspondence, even for meshes with near-degenerate elements. Our starting point is the framework of normal coordinates from geometric topology, which we extend to the broader set of operations needed for mesh processing (vertex insertion, edge splits, etc.). The resulting data structure can be used as a drop-in replacement for earlier schemes, automatically improving reliability across a wide variety of applications. As a stress test, we successfully compute an intrinsic Delaunay refinement and associated subdivision for all manifold meshes in the Thingi10k dataset. In turn, we can compute reliable and highly accurate solutions to partial differential equations even on extremely low-quality meshes. [ABSTRACT FROM AUTHOR]

Abstract We present a mixed reality-based assistive system for shading paper sketches. Given a paper sketch made by an artist, our interface helps inexperienced users to shade it appropriately. Initially, using a simple Delaunay-triangulation based inflation algorithm, an approximate depth map is computed. The system then highlights areas (to assist shading) based on a rendering of the 2.5-dimensional inflated model of the input contour. With the help of a mixed reality system, we project the highlighted areas back to aid users. The hints given by the system are used for shading and are smudged appropriately to apply an artistic shading to the sketch. The user is given flexibility at various levels to simulate conditions such as height and light position. Experiments show that the proposed system aids novice users in creating sketches with impressive shading.

Extensive studies have been conducted on the Dijkstra algorithm owing to its bright prospect. However, few of them have studied the surface path planning of mobile robots. Currently, some application fields (e.g., wild ground, planet ground, and game scene) need to solve the optimal surface path. This paper proposes an extended Dijkstra algorithm. We utilize the Delaunay triangulation to model the surface environment. Based on keeping the triangle side length unchanged, the triangle mesh on the surface is equivalently converted into a triangle on the two-dimensional plane. Through this transformation, we set up the two-dimensional developable passable channel of the surface and solve the optimal route on this channel. Traversing all the two-dimensional developable and passable paths of the surface, we can get the shortest route among all the optimal paths. Then the inverse transformation from the two-dimensional plane coordinates to the corresponding surface coordinates obtains the surface optimal path. The simulation results show that, compared with the traditional Dijkstra algorithm, this method improves the accuracy of the surface optimization path in single-robot single-target and multi-robot multi-target path planning tasks.

Delaunay triangulation is a main topic in computer graphics. Various types of new requirements have appeared during the development of parallel triangulation algorithms, e.g., updating the triangulation incrementally given a set of increasing points. Existing incremental triangulation algorithms do not support for inserting points outside of the triangulation. This paper proposes the expansion of triangulation and designs an incremental triangulation algorithm TID (truly incremental Delaunay) supporting for inserting any number of points with any distribution into an existing triangulation for any time. TID is designed to produce a unique triangulation result for any distribution of points. Experimental evaluation results on TID show that TID has higher computational efficiency than existing algorithms and introduces low computational overhead. In addition, TID has already been used in parallel triangulation algorithm as local triangulation algorithm.

Collapse is a common cartographic generalization operation in multi-scale representation and cascade updating of vector spatial data. During transformation from large- to small-scale, the dual-line river shows progressive collapse from narrow river segment to line. The demand for vector spatial data with various scales is increasing; however, research on the progressive collapse of dual-line rivers is lacking. Therefore, we proposed a progressive collapse method based on vector spatial data. First, based on the skeleton graph of the dual-line river, the narrow and normal river segments are preliminarily segmented by calculating the width of the river. Second, combined with the rules of cartographic generalization, the collapse and exaggeration priority strategies are formulated to determine the handling mode of the river segment. Finally, based on the two strategies, progressive collapse of dual-line rivers is realized by collapse and exaggeration of the river segment. Experimental results demonstrated that the progressive collapse results of the proposed method were scale-driven, and the collapse part had no burr and topology problems, whereas the remaining part was clearly visible. The proposed method can be better applied to progressive collapse of the dual-line river through qualitative and quantitative evaluation with another progressive collapse method.

In an era of high penetration of renewable energy, accurate photovoltaic (PV) power forecasting is crucial for balancing and scheduling power systems. However, PV power output has uncertainty since it depends on stochastic weather conditions. In this paper, we propose a novel short-term PV forecasting technique using Delaunay triangulation, of which the vertices are three weather stations that enclose a target PV site. By leveraging a Transformer encoder and gated recurrent unit (GRU), the proposed TransGRU model is robust against weather forecast error as it learns feature representation from weather data. We construct a framework based on Delaunay triangulation and TransGRU and verify that the proposed framework shows a 7–15% improvement compared to other state-of-the-art methods in terms of the normalized mean absolute error. Moreover, we investigate the effect of PV aggregation for virtual power plants where errors can be compensated across PV sites. Our framework demonstrates 41–60% improvement when PV sites are aggregated and achieves as low as 3–4% of forecasting error on average.

For proper rehabilitation planning and appropriate technology selection for airport pavements, information on the layer thicknesses is important. Pavement layer thickness can be determined by ground penetrating radar (GPR). GPR data is usually displayed in distance vs thickness diagrams. These two-dimensional displays do not utilise the full potential of the three-dimensional (3D) information of GPR data. To appropriately represent the data, the display should be 3D, as well. The aim of this study is to present a process for creating a 3D model and spatial representation of asphalt concrete (AC) overlay thickness. The 3D model of the AC overlay surface is generated based on the Delaunay triangulation of interpreted GPR data. The 3D model is presented on contour and band maps, whose accuracy is evaluated by comparing the thicknesses displayed by the contour maps with those measured in core samples. The calculated mean relative error of the contour map is 7.2%. The band map is used to identify sections of equal thickness or to analyse predefined sections, to select the appropriate rehabilitation technology. The combination of the interpreted GPR data and Delaunay triangulation successfully compensates for the lack of 3D GPR, in terms of the spatial representation of layer thickness. [ABSTRACT FROM AUTHOR]

Aiming at the problem tha11raditional geometrie methods are difficult to apply to probabilistic perception models in the process of secondary deployment of nodes in wireless sensor networks, a WSN area coverage optimization scheme based on Delaunay triangulation strategy is proposed. Firstly, Delaunay triangulation is performed on randomly scattered static nodes and the edge vertices in the monitoring area to obtain a static node triangulation. Combined with the probabilistic perception model, it is proved that there are completely uncovered areas inside triangles. Secondly, the selected triangle centroid set is used as the initial solution set of the particle swarm optimization algorithm, and the improved particle swarm optimization algorithm is used to complete the secondary deployment of mobile nodes to achieve the purpose of repairing the coverage loophole. The simulation experiment proves that this optimization scheme can effectively repair the coverage loopholes and significantly improve the regional coverage. [ABSTRACT FROM AUTHOR]

Proteins' three‐dimensional (3D) structures are analyzed traditionally using geometric descriptors such as torsional angles and inter‐atomic distances. In this study a measure that is borrowed from computational geometry, aspect ratio of each tetrahedron in alpha shapes of proteins, is utilized. This geometric descriptor differentiates alpha and beta structural classes of proteins when combined with principal components analysis. The method converts the structures of individual proteins, 3D coordinates of the atoms, to points on a plane. It has a high degree of accuracy in differentiating R and T structures of hemoglobin. Therefore, it is anticipated that the geometric measure can be used successfully in a method that is extended to solve classification problems in machine learning. [ABSTRACT FROM AUTHOR]

Road intersections are essential to road networks. How to precisely recognize road intersections based on GPS data is still challenging in intelligent transportation systems. Road intersection recognition involves detecting intersections and recognizing its scope. There are few works on intersections’ scope recognition. The existing methods always focus on road intersection detection. It includes two parts: one is selecting turning points from GPS data and extracting their geometric features, another is clustering them into center coordinates of road intersections. However, the accuracy of road intersection detection still has improvement room due to two drawbacks: (1) Besides geometric features, spatial features explored from GPS data and the interactions among all features are also important to represent intersections’ semantics more accurately, and (2) How to capture the points around intersections for clustering has great impact on the accuracy of intersection detection. To solve the preceding problems, we propose a novel approach for road intersection recognition via combining a classification model and clustering algorithm based on GPS data, which involves detecting the center coordinate and computing the radius of the intersection. Firstly, we distil geometric features and spatial features from historical GPS points. These features are inputted into the Extreme Deep Factorization Machine (xDeepFM) model which is applied for capturing the GPS points nearby road intersections. Secondly, the preceding points are clustered into center coordinates of road intersections by the Density-Based Spatial Clustering of Applications with Noise algorithm (DBSCAN). Thirdly, we present a new method of radius computing by integrating Delaunay triangulation with circle shape structure. Experiments are carried out on the GPS data of Chengdu, China. Compared with some state-of-the-art methods, our approach achieves higher accuracy on road intersection recognition based on GPS data. The precision, recall, and f-measure of our proposed center coordinates detection method are respectively 99.0%, 92.7%, and 95.8% when the matching area’s radius is 30 m. Moreover, the error of the proposed radius calculation method is less than 26.5%.

Wireless Sensor Networks (WSNs) enhance the ability to sense and control the physical environment in various applications. The functionality of WSNs depends on various aspects like the localization of nodes, the strategies of node deployment, and a lifetime of nodes and routing techniques, etc. Coverage is an essential part of WSNs wherein the targeted area is covered by at least one node. Computational Geometry (CG) -based techniques significantly improve the coverage and connectivity of WSNs. This paper is a step towards employing some of the popular techniques in WSNs in a productive manner. Furthermore, this paper attempts to survey the existing research conducted using Computational Geometry-based methods in WSNs. In order to address coverage and connectivity issues in WSNs, the use of the Voronoi Diagram, Delaunay Triangulation, Voronoi Tessellation, and the Convex Hull have played a prominent role. Finally, the paper concludes by discussing various research challenges and proposed solutions using Computational Geometry-based techniques.

Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O(n2+ε), for any ε > 0, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions. [ABSTRACT FROM AUTHOR]

This paper presents a new method for generating the random fiber distributions of carbon fiber reinforced plastic with high volume fraction. The novelty is that an adaptive fiber shaking module is developed on the basis of Delaunay triangulation and combined with the proposed algorithm. The adaptability is to realize coordination between the parameters of fiber volume fraction and fiber spacing, in order to overcome the jamming limit and eliminate the unreasonable resin-rich zone that may appear at the boundary of the microstructures. The maximum fiber volume fraction reached is 67.43%. Statistical analysis is conducted on the generated microstructures, and there is a good agreement by comparing it with the statistical results of random sequential expansion algorithm and completely spatial random pattern. Finite element analysis is also performed to predict the elastic properties of the generated microstructures. It shows that a maximum absolute error is only 7.354% in elastic property by comparing with the experimental and simulation results in literatures. The proposed algorithm contributes to the further researches on the strength and micro-damage evolution of carbon fiber reinforced plastic.

Training a support vector machine (SVM) on large datasets is a slow daunting process. Further, SVM becomes slow in the testing phase, due to its large number of support vectors (SVs). This paper proposes an effective geometric algorithm based on construction of Delaunay triangulation (DT) algorithm using Quickhull algorithm with a novel strategy to exactly identify and extract the boundary data points laid between the two classes of a dataset, and later uses these most informative data points as a reduced dataset to solve various SVM algorithms and proposes new DT-SVM algorithms Two synthetic datasets with the size of 1K incrementally up to 500K datasets are generated to extensively verify the effectiveness of the proposed DT-SVM algorithms over various data sizes and for further assessment, the most efficient version of proposed DT-SVM is applied on well-known benchmark datasets from UCI Machine Learning Repository. Two variant of sequential minimization optimization (SMO) decomposition methods, in addition to Least Square form of SVM are implemented to present the scalability of new DT-SVM algorithms in linear/nonlinear separable/non-separable large low dimensional datasets. Moreover, the most efficient version of the proposed algorithm is compared to RCH-SK as a known geometric approach in the SVM literature. The results demonstrate that while the proposed approach improves the scalability of DT-SVM in large low dimensional datasets, it leads SVM algorithms to maintain the accuracy in an acceptable range with considerably lower time in both training and testing phases with using a noticeably fewer number of SVs.

User-preference based multi-objective evolutionary algorithms (MOEAs) have attracted much attention recently because it helps save computational cost, make better use of the knowledge offered by the decision-maker, and offer more insight into solutions in the region of interest (ROI). Weight vectors based MOEAs can be converted to their user-preference based versions by offering a set of evenly distributed weight vectors located in ROI. Yet existing weight design methods can only generate weight vectors in the whole unit plane in the weight space. To generate an arbitrary number of weight vectors in ROI, this paper proposes a tri-objective user-preference based uniform weight design method using Delaunay Triangulation (PUWD-DT), so that weight vectors can be fine-tuned to uniformity in ROI. Furthermore, the proposed PUWD-DT based preference method with the achievement scalarizing function is assembled into MOEA/D to convert it into its user-preference based version (MOEA/D+PUWD-DT) and the convergence of population in ROI for optimization problems with irregular shaped Pareto front is also promoted. Finally, the MOEA/D+PUWD-DT is applied to the reservoir flood control operation problem, and our experimental results indicate that the proposed preference-based MOEA method performs better than the state-of-the-art. [ABSTRACT FROM AUTHOR]

The ability of granular materials to retain fine particles transported within their void space by seepage flow depends strongly on the geometric characteristics of their pore network (pore sizes and constriction sizes). Hence, characterizing the pore network of a granular assembly obtained by means of a micro-tomography scanning or a numerical discrete simulation is of great importance in assessment of its filtration efficiency. Here, we determine characteristics of the pore network of virtual samples composed of spherical particles simulated by using the DEM. A new criterion is proposed to merge neighboring tetrahedra issued from the weighted Delaunay triangulation. To do so, we extend the concept of inscribed void sphere, initially defined for each tetrahedron, to each polyhedral sub-domain constituted of merged tetrahedra. This inscribed void sphere fits the best the void space within the sub-domain. Flat tetrahedra are first eliminated by a primary merging procedure taking into account two basic geometric conditions required for each pore. Adjacent sub-domains are then merged depending on the level of overlap between their inscribed void spheres. The pore size distributions and constriction size distributions (CSD) of granular samples with different grain size distributions obtained with the new merging criterion are compared to those given by two other criteria often used in the literature. The new criterion allows us to reduce greatly the inherent subjectivity in characterizing the granular pore network and to remediate the drawbacks of the two considered criteria in the literature. Moreover, CSDs given by these different criteria tend to converge for gap-graded and widely graded materials. The CSDs obtained with the new merging criterion are used to estimate the controlling constriction sizes D c ∗ of the considered samples, and the estimated values of D c ∗ are compared to Kenney and Lau's empirical rule. [ABSTRACT FROM AUTHOR]

This paper addresses the maintenance of a communication network in which mobile agents are connected to their nearest neighbours. While all agents are able to move individually, the geometrical relation to each other changes along their trajectories. The main idea is to develop distributed algorithms which enable the agents to monitor and to switch communications links in real time so that the overall network topology equals a Delaunay triangulation at any time. It is shown which information has to be stored locally by each agent and exchanged among the agents via digital communication. The paper closes with an experimental evaluation of the proposed methods. [ABSTRACT FROM AUTHOR]

We address the problems of constructing the Voronoi diagram (VD) and Delaunay triangulation (DT) of points in the plane with mutually dependent location uncertainties, testing their stability, and computing their components. Point coordinate uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), a deterministic, expressive and computationally efficient first order linear approximation of geometric uncertainty that supports parametric dependencies between point locations. We define an uncertain three-point circle and its properties and present in-circle-test algorithms for the dependent and the independent cases whose respective time complexity is O (P 4 (k)) and O (k log k) , where k is the number of parameters that describe the points location uncertainty and P 4 (k) is the complexity of quartic k -variable optimization. We define the uncertain VD and DT of n LPGUM points and show that an unstable VD may have an exponential number of topologically different instances. We describe algorithms for testing VD and DT stability whose time complexity is O (n P 4 (k)) and O (n k log k) for the dependent and independent cases when the nominal (exact) VD is given. We present algorithms to compute the vertices, edges, and faces of uncertain VD and DT for the independent case whose complexity is O (n k 2 log k + n log n) time and O (n k) space. Finally, we describe algorithms for answering exact and uncertain point location queries in a stable uncertain VD and for dynamically updating it in O (k 2 log k + log n) and O (k 2 log k + log n + P 4 (k)) average case time complexity for the independent and dependent cases. [ABSTRACT FROM AUTHOR]

The distribution of fibers in composite manufacturing significantly affects fiber bundle permeability, a crucial factor for resin impregnation and void formation, which determines final product quality. However, as the industry increasingly seeks composite materials characterized by high fiber volume fractions, the existing numerical analysis methodologies employed for predicting permeability require a considerable computational cost. In this study, the permeability prediction model was developed using a fluid domain simplification technique based on Delaunay triangulation. The inter-fiber flow was approximated using a lubrication model, and continuity was ensured using a circuit analogy. This model can explain stochastic permeability characteristics according to fiber distribution and accurately predicts the permeability regardless of the distance between fibers. Additionally, compared to existing computational fluid dynamics simulations, it achieved an incredible accuracy of 97.74% and reduced computational costs by an average of 1,700 times. [ABSTRACT FROM AUTHOR]

In article presents algorithmic for a reconnaissance and combat unmanned flying vehicle (UFV) group pre-flight planning. The algorithms, which we elaborated, includes: algorithm, involved for mission target decision, membership selection. Discussing algorithm is based on analytical probabilistic models, providing evaluation of UAF group efficiency operation, considering UAF reliability as well as on board navigation and weapon facility performances; algorithm of UAF routes at the stages of group motion to meeting point and further movement to target area. Developed algorithm provides definition both direction and velocity of UAF, considering actual environment condition and dangerous of UAF recognition by radar, acoustic or infrared facilities of enemy; algorithms of UAF group operation scheduling at the mission target area.

Image deformation has ubiquitous usage in multimedia applications. It morphs one image into another through a seamless transition. Existing techniques either mainly focus on the correspondence mapping of interior features of the objects in two images, without considering object contours, or sketch contours manually, resulting in tedious work for users. Thus, we propose a 2D image deformation method, which extracts object contours automatically, considers both inner features and contours as constraints and preserves image features in terms of visual importance. Our method first automatically extracts the object contours in the source and target images and then allows users to sketch some interior features in both the images. Then, our method tessellates two images to generate two triangular meshes and builds a guaranteed bijective mesh mapping between them. We also prove the bijectivity of our mesh mapping and discuss its other desirable properties. Then, our method generates the intermediate images between the source and target images by calculating the intermediate meshes and pixels of each intermediate image. Our method realizes automatic contour extraction, provides an intuitive user interface and utilizes harmonic maps to establish a bijective mesh mapping. Therefore, it preserves more significant features with less distortion and works well for many image deformation cases in real time.

Negative selection algorithm (NSA) is an important detector generation algorithm of artificial immune system (AIS). Traditional NSAs randomly generate detectors in the whole antigen space without considering the distribution of self/non-self antigens, therefore it is difficult for detectors to cover the whole antigen space evenly and a seriously time-consuming self-tolerance process is required. Aiming at the problem, we proposed a novel NSA based on antigen space triangulation coverage (ASTC) called ASTC-RNSA. In order to avoid the randomness in traditional NSAs, the proposed algorithm employed Delaunay Triangulation method from computational geometry to divide the self space into simplicial cells, which are utilized to determine the detector positions. Then, the overlaps between simplicial cells and self-antigens are removed to form a set of triangulation coverage areas. Finally, immune detectors which only covered non-self antigens space are generated in each triangulation coverage area. After Delaunay triangulation of antigen space, ASTC-RNSA can directly determine sui detector positions and avoid the time-consuming self-tolerance process of traditional NSAs. The analysis result shows that the time complexity of ASTC-RNSA is reduced from traditional exponential level to logarithmic level. The experimental results on several UCI datasets and artificial datasets show that the proposed algorithm can achieve more than 10 times the detector generation efficiency while maintaining similar detection performance with the most widely used representative typical algorithm, V-Detector.

The quality of the filling algorithm in additive manufacturing directly affects the strength of the part. The commonly used 3D printing filling algorithm at this stage is the classic filling algorithm. The density of each part in the filling region is the same, and there is a cavity structure in the transverse direction, which makes the strength of the part in the transverse direction lower. Therefore, this paper proposed a new filling algorithm—variable density filling algorithm based on Delaunay triangulation. First, we performed concave-polygon-convex decomposition on the filling area to form printing sub-regions; then, the filling density value was set according to the required intensity of each region, and we used the Poisson disk sampling algorithm to generate the filling point set. Finally, Delaunay triangulation was performed on the generated point set to generate filled traces. The comparison with the two commonly used classical filling algorithms proves that the algorithm can improve the strength of the part to a certain extent, and the printing time and the consumption of consumables will not increase significantly.

Marking the tree canopies is an unavoidable step in any study working with high-resolution aerial images taken by a UAV in any fruit tree crop, such as olive trees, as the extraction of pixel features from these canopies is the first step to build the models whose predictions are compared with the ground truth obtained by measurements made with other types of sensors. Marking these canopies manually is an arduous and tedious process that is replaced by automatic methods that rarely work well for groves with a thick plant cover on the ground. This paper develops a standard method for the detection of olive tree canopies from high-resolution aerial images taken by a multispectral camera, regardless of the plant cover density between canopies. The method is based on the relative spatial information between canopies.The planting pattern used by the grower is computed and extrapolated using Delaunay triangulation in order to fuse this knowledge with that previously obtained from spectral information. It is shown that the minimisation of a certain function provides an optimal fit of the parameters that define the marking of the trees, yielding promising results of 77.5% recall and 70.9% precision.

Many authors have been working on approaches that can be applied to social robots to allow a more realistic/comfortable relationship between humans and robots in the same space. This paper proposes a new navigation strategy for social environments by recognizing and considering the social conventions of people and groups. To achieve that, we proposed the application of Delaunay triangulation for connecting people as vertices of a triangle network. Then, we defined a complete asymmetric Gaussian function (for individuals and groups) to decide zones where the robot must avoid passing. Furthermore, a feature generalization scheme called socialization feature was proposed to incorporate perception information that can be used to change the variance of the Gaussian function. Simulation results have been presented to demonstrate that the proposed approach can modify the path according to the perception of the robot compared to a standard A* algorithm.

The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can be either cut entirely (complete cutting approach) or partially (partial cutting approach) before cutting the next polygon. This work solves the cutting path determination problem using the partial cutting approach. The proposed approximation algorithm uses the concepts of ma tching, s panning tree, and tri angulation, and is hence termed as MASTRI. The MASTRI algorithm has a time complexity of O(n logn) where n is the total number of vertices of all the polygons. The cutting path computed by the MASTRI algorithm is guaranteed to be within a factor of 3/2 of optimum travel distance of the cutter. No other algorithm has been developed for the partial cutting approach which runs in polynomial time. The MASTRI algorithm is evaluated on 285 input problems, of which 192 problems are randomly generated, and 93 problems are taken from literature. The experimental analysis shows that the MASTRI algorithm computes the cutting path in a very short amount of time. The comparison of MASTRI algorithm with existing works in the literature shows that the MASTRI algorithm gives a shorter cutting path in less time. The MASTRI algorithm can be used for computing cutting path in industries like sheet metal cutting. [ABSTRACT FROM AUTHOR]