Search

ABSTRACT Reconstructing and processing 3D objects are activities in the research field of computer graphics, image processing and computer vision. The 3D objects are processed based on geometric modelling (a branch of applied mathematics and computational geometry) or machine learning algorithms based on image processing. The computation of geometrical objects includes processing the curves and surfaces, subdivision, simplification, meshing, holes filling or reconstructing the 3D surface's objects on both point cloud data and triangular mesh. While the machine learning methods are developed using deep learning models. With the support of 3D laser scan devices and LiDAR techniques, the obtained dataset is close to the original shape of the real objects. Besides, photography and its application based on modern techniques in recent years help us collect data and process the 3D models more precisely. This article proposes a new method for filling holes on the 3D object's surface based on automatic segmentation. Instead of filling the hole directly as the existing methods, we now subdivide the hole before filling it. The hole is first determined and segmented automatically based on the computation of its local curvature. It is then filled on each part of the hole to match its local curvature shape. The method can work on both 3D point cloud surfaces and triangular mesh surfaces. Compared to the state‐of‐the‐art (SOTA) methods, our proposed method obtained higher accuracy of the reconstructed 3D objects. [ABSTRACT FROM AUTHOR]

Laser directed energy deposition (LDED), a class of additive manufacturing (AM) processes, has immense potential to be used for various engineering applications to build components with medium to high complexity. However, dimensional deviations from intended values and inadequate surface quality of the built parts limit its wide deployment. The present work reports the development of an adaptive tool path trajectory platform to correct the dimensional inaccuracies in-situ to build high-quality components using LDED. The study deploys a laser line scanner to scan the part after the deposition of the definite number of layers followed by the detection of concave, convex, and flat surfaces using deep learning. Further, a novel adaptive trajectory planning algorithm is deployed by using three different strategies to control material deposition on concave, convex, and flat surfaces. The material deposition is controlled by using adaptive scanning speed control (ASSC), and a combination of laser on–off and scanning speed control (ASSLC). Subsequently, the built geometries are subjected to geometric, microstructure, and mechanical characterizations. It is observed that the deviation of the part was reduced by 30%, and 27.5% using ASSC and ASSLC, respectively. The structures built using the three strategies show some micropores at isolated locations. The microstructure is mainly cellular under all conditions with a similar average microhardness of ~ 210 HV. The study provides an integrated and comprehensive approach for building high-quality large-scale components using LDED with minimal dimensional deviation from the original CAD model. [ABSTRACT FROM AUTHOR]

Convex hull computation is a critical problem in computational geometry with a wide range of applications. Existing approaches focus on separate algorithms for calculating the convex hull of polygons and curvilinear polygons, leaving room for improvement in terms of efficiency and accuracy. To address these limitations, we propose the "Simulation of Progressively Supporting Elastic lines" (SPSEL) algorithm, which leverages the physical properties of elastic lines and their progressive support process. The SPSEL algorithm efficiently computes the convex hull of generic polygons that contain both straight and curved edges. This paper provides a comprehensive overview of the SPSEL algorithm, including its terminology, overall process, and specific methods used in key algorithmic steps. Comparative tests are conducted to assess its performance, and the experimental results demonstrate the superior performance of the SPSEL algorithm compared to the Johnstone's algorithm, specifically designed for curved convex hulls. The SPSEL algorithm exhibits efficiency and effectiveness in handling various types of generic polygons, showcasing its potential for achieving linear-time operations. Furthermore, the paper discusses the possibilities of extending the SPSEL algorithm to address the computation of convex envelopes for 3D shapes, a challenging research area with theoretical and practical implications. Overall, the SPSEL algorithm offers an advanced solution for computing convex hulls of polygons with both straight and curved edges, demonstrating improved efficiency and accuracy compared to existing methods. These findings contribute to the field of computational geometry and have broad implications for applications requiring convex hull computation in diverse domains. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of computing the optimal stacking of two monotone polytopes P and Q in R d . A monotone polytope in R d is defined as a polytope whose intersection with any line parallel to the last coordinate axis x d is connected, and the stacking of P and Q is defined as a translation of Q, such that "Q touches P from above". To evaluate the stack, we use three different scoring criteria: (1) the height of the stack, (2) the maximum pointwise distance along the x d -axis, and (3) the volume between P and Q. We propose exact algorithms to compute the optimal stacking for each scoring criterion. [ABSTRACT FROM AUTHOR]

Given a set of dot pattern point set P with the size n in the plane, we propose a Delaunay triangulation-based shape reconstruction algorithm, entitled prudent carving, that can reconstruct the inner boundaries (holes) and outer boundaries of P with the same approach. Our prudent carving algorithm is a parameter-free algorithm that has the ability to detect multiple components, sharp corners, and nested holes independent from the number of them in the total O (n log n) time. The qualitative and quantitative comparison of the results with the state-of-the-art algorithms shows that the prudent carving algorithm provides an enhancement over the previously best-known algorithms for reconstructing the boundaries of points. [ABSTRACT FROM AUTHOR]

In several applications, ranging from computational geometry and finite element analysis to computer graphics, there is a need to approximate functions defined on triangular domains rather than rectangular ones. For this purpose, frequently used interpolation methods include barycentric interpolation, piecewise linear interpolation, and polynomial interpolation. However, the use of polynomial interpolation methods may suffer from the Runge phenomenon, affecting the accuracy of the approximation in the presence of equidistributed data. In these situations, the constrained mock-Chebyshev least squares approximation on rectangular domains was shown to be a successful approximation tool. In this paper, we extend it to triangular domains, by using both Waldron and discrete Leja points. This paper is dedicated to Len Bos on the occasion of his retirement. Len, for us, is a master of mathematics and also a big friend. He introduced us to the fascinating world of "finding good interpolation nodes and effective interpolation strategies", mostly in the multivariate setting. The set of points we are using in this paper, Waldron and Leja, have been introduced to us by him and we hope that this note can be of some interest for him and all people working on approximation theory. [ABSTRACT FROM AUTHOR]

The paper deals with the issue of determining the optimal setting of input variables in Ansys CFX for modeling pump flow in turbine operation (PAT). The pump model was created in Autodesk Inventor. The mesh for numerical simulations was created using Ansys Fluent Meshing, considering the mesh quality parameters' skewness and aspect ratio. The Ansys CFX computational model was experimentally verified on an actual pump by measuring the performance parameters on a test circuit and using the PIV (particle image velocimetry) method. The research indicated that the most suitable setting for the model input variables was the inlet pressure and PAT flow rate combination. Another option was to adjust the pressure at the pump inlet and outlet. However, the calculation time in this case was up to 30% longer. The comparison of the model results with the experiment showed that the deviations in the numerical model performance values did not exceed 10% of the values measured on the test circuit. Only the calculated torque was 1.2 ± 0.13 Nm higher on average than the torque measured on the test circuit. This difference is most likely due to the simplification of the geometry of the computational mesh in order to reduce the computation time. [ABSTRACT FROM AUTHOR]

VORO++ is a software library written in C++ for computing the Voronoi tessellation, a technique in computational geometry that is widely used for analyzing systems of particles. VORO++ was released in 2009 and is based on computing the Voronoi cell for each particle individually. Here, we take advantage of modern computer hardware, and extend the original serial version to allow for multithreaded computation of Voronoi cells via the OpenMP application programming interface. We test the performance of the code, and demonstrate that it can achieve parallel efficiencies greater than 95% in many cases. The multithreaded extension follows standard OpenMP programming paradigms, allowing it to be incorporated into other programs. We provide an example of this using the VoroTop software library, performing a multithreaded Voronoi cell topology analysis of up to 102.4 million particles. Program summary: Program title: VORO++ CPC Library link to program files: https://doi.org/10.17632/tddc4w4zkk.1 Developer's repository link: https://github.com/chr1shr/voro Licensing provisions: BSD 3-clause (with LBNL modification) Programming language: C++ External routines/libraries: OpenMP Nature of problem: Multithreaded computation of the Voronoi tessellation in two and three dimensions Solution method: The VORO++ library is built around several C++ classes that can be incorporated into other programs. The two largest components are the container. classes that spatially sort input particles into a grid-based data structure, allowing for efficient searches of nearby particles, and the voronoicell. classes that represent a single Voronoi cell as an arbitrary convex polygon or polyhedron. The Voronoi cell for each particle is built by considering a sequence of plane cuts based on neighboring particles, after which many different statistics (e.g. volume, centroid, number of vertices) can be computed. Since each Voronoi cell is calculated individually, the Voronoi cells can be computed using multithreading via OpenMP.

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (in SIAM Journal on Computing, 1999) gave an algorithm of O(n logn) time and O(n logn) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm,Wang (in SODA’21) reduced the space toO(n) while the runtime of the algorithm is still O(n logn). In this article, we present a new algorithm of O(n + h logh) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. The algorithm is better than the previous work when h is relatively small. Our algorithm builds a shortest path map for a source point s so that given any query point t, the shortest path length from s to t can be computed in O(logn) time and a shortest s-t path can be produced in additional time linear in the number of edges of the path. [ABSTRACT FROM AUTHOR]

In the semialgebraic range searching problem, we are given a set of n points in ℝd, and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with S(n)Q(n)d=Õ(nd), where the Õ(⋅) notation hides polylogarithmic factors and this trade-off is tight (up to no(1) factors). In particular, there exist “low space” structures that use O(n) space with O(n1-1/d) query time [8, 25] and “fast query” structures that use O(nd) space with O(log n) query time [9]. However, for general semialgebraic ranges, only “low space” solutions are known, but the best solutions [7] match the same trade-off curve as simplex queries, with O(n) space and Õ(n1−1/d) query time. It has been conjectured that the same could be done for the “fast query” case, but this open problem has stayed unresolved. Here, we disprove this conjecture. We give the first nontrivial lower bounds for semialgebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting, with Q(n) query time must use S(n)=...(n³/Q(n)5) space, where the ...(⋅) notation hides no(1) factors, meaning, for Q(n)=logO(1)n, ...(n³) space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by {(x,y)∈R²:P(x)≤y≤P(x)+w}, where P(x)=∑i=0Δaixi is a univariate polynomial of degree Δ and a0,…,aΔ,w are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of ...(nΔ+1/Q(n)(Δ+3)Δ/2), which implies that for Q(n)=logO(1)n, we must use ...(nΔ+1) space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use ...(n2/3) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case. [ABSTRACT FROM AUTHOR]

An isogeometric topology optimization (ITO) model for multi-material structures under thermal-mechanical loadings using neural networks is proposed. In the proposed model, a non-uniform rational B-spline (NURBS) function is employed for geometric description and analytical calculation, which realizes the unification of the geometry and computational models. Neural networks replace the optimization algorithms of traditional topology optimization to update the relative densities of multi-material structures. The weights and biases of neural networks are taken as design variables and updated by automatic differentiation without derivation of the sensitivity formula. In addition, the grid elements can be refined directly by increasing the number of refinement nodes, resulting in high-resolution optimal topology without extra computational costs. To obtain comprehensive performance from ITO for multi-material structures, a weighting coefficient is introduced to regulate the proportion between thermal compliance and compliance in the loss function. Some numerical examples are given and the validity is verified by performance analysis. The optimal topological structures obtained based on the proposed model exhibit both excellent heat dissipation and stiffness performance under thermal-mechanical loadings. [ABSTRACT FROM AUTHOR]

Driven by the growing interest of the scientific community and the proliferation of research in this field, cranial implants have seen significant advancements in recent years regarding design techniques, structural optimisation, appropriate material selection and fixation system method. Custom implants not only enhance aesthetics and functionality, but are also crucial for achieving proper biological integration and optimal blood irrigation, critical aspects in bone regeneration and tissue health. This research aims to optimize the properties of implants designed from triply periodic minimal surface structures. The gyroid architecture is employed for its balance between mechanical and biological properties. Experimental samples were designed varying three parameters of the surface model: cell size, isovalue and shape factor. Computational simulation tools were used for determining the relationship between those parameters and the response variables: the surface area, permeability, porosity and Young modulus. These tools include computer aided design, finite element method and computational fluid dynamics. With the simulated values, the corresponding regression models were fitted. Using the NSGA-II, a multi-objective optimisation was carried out, finding the Pareto set which includes surface area and permeability as targets, and fulfil the constraints related with the porosity and Young modulus. From these non-dominated solutions, the most convenient for a given application was chosen, and an optimal implant was designed, from a patient computed tomography scan. An implant prototype was additively manufactured for validating the proposed approach. [ABSTRACT FROM AUTHOR]

Precise monitoring of individual crop growth and health status is crucial for precision agriculture practices. However, traditional inspection methods are time-consuming, labor-intensive, prone to human error, and may not provide the comprehensive coverage required for the detailed analysis of crop variability across an entire field. This research addresses the need for efficient and high-resolution crop monitoring by leveraging Unmanned Aerial Vehicle (UAV) imagery and advanced computational techniques. The primary goal was to develop a methodology for the precise identification, extraction, and monitoring of individual corn crops throughout their growth cycle. This involved integrating UAV-derived data with image processing, computational geometry, and machine learning techniques. Bi-weekly UAV imagery was captured at altitudes of 40 m and 70 m from 30 April to 11 August, covering the entire growth cycle of the corn crop from planting to harvest. A time-series Canopy Height Model (CHM) was generated by analyzing the differences between the Digital Terrain Model (DTM) and the Digital Surface Model (DSM) derived from the UAV data. To ensure the accuracy of the elevation data, the DSM was validated against Ground Control Points (GCPs), adhering to standard practices in remote sensing data verification. Local spatial analysis and image processing techniques were employed to determine the local maximum height of each crop. Subsequently, a Voronoi data model was developed to delineate individual crop canopies, successfully identifying 13,000 out of 13,050 corn crops in the study area. To enhance accuracy in canopy size delineation, vegetation indices were incorporated into the Voronoi model segmentation, refining the initial canopy area estimates by eliminating interference from soil and shadows. The proposed methodology enables the precise estimation and monitoring of crop canopy size, height, biomass reduction, lodging, and stunted growth over time by incorporating advanced image processing techniques and integrating metrics for quantitative assessment of fields. Additionally, machine learning models were employed to determine relationships between the canopy sizes, crop height, and normalized difference vegetation index, with Polynomial Regression recording an R-squared of 11% compared to other models. This work contributes to the scientific community by demonstrating the potential of integrating UAV technology, computational geometry, and machine learning for accurate and efficient crop monitoring at the individual plant level. [ABSTRACT FROM AUTHOR]

Consensus measures are commonly used in research and typically rely on Likert scales, focusing on the 5-point Likert scale. One of the main attributes of this scale is that it is designed to work for any size. However, many of the researchers used the 5-point Likert scale. While some researchers have attempted to generalize consensus measures to work in two-dimensional space, this approach remains complex and challenging. In this work, we generalize the measure of consensus to work for seven Likert scales using the computational geometry of four-dimensional concepts. A numerical example and some related concepts are provided. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to discuss a study aiming to optimize the performance of a DLR-type scramjet engine using computational fluid dynamics (CFD). For this purpose, the response surfaces technique is employed to carry out a multi-objective optimization of the strut geometry used in this engine. In the simulation, strut length and width are considered as design variables. Thrust and combustion efficiency are also constituted as objective parameters. Response surfaces are created using two methods: Kriging and nonparametric regression (NPR). The obtained results indicate a higher accuracy of the Kriging approach. The optimization results show that in the best case the amount of thrust can be increased up to 62.618 N, which is 5.6% more than the base value. Also, the combustion efficiency can be raised to a maximum value of 74.4%, which is 12.37% higher than the base value. In order to determine which design variables have a more significant effect on objective factors, sensitivity analysis has been performed. This analysis revealed that the strut width has more significant effect on the combustion efficiency, while the thrust was more dependent on the strut length. [ABSTRACT FROM AUTHOR]

This paper investigates the geometric patterns inherent in Arabic poetry rhythms, uncovering attributes that likely contribute to their historical popularity. Through comprehensive analysis, we identified a combination of computational geometric features that seem to correlate with defining a rhythm's attraction in Arabic poetry. These features can be used to generate similar but new appealing poetry rhythms. While there are multiple studies on the geometry of musical rhythms, our research offers a novel perspective by applying these geometric concepts to poetry rhythms, aiming to contribute to the understanding of rhythmic patterns across diverse creative domains. To the best of our knowledge, our work is the first attempt to transfer the geometric analysis of rhythms to Arabic poetry rhythms. Moreover, our findings hint at potential connections between the rhythms of Arabic poetry and English song lyrics. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, the maximum triangle problem asks for finding a triangle with three vertices in P that encloses the maximum number of points from P. While the problem is easily solvable in O(n³) time, it has been open whether a subcubic solution is possible. In this paper, we show that the problem can be solved in o(n3) time, using a reduction to min-plus matrix multiplication. We also provide some improved approximation algorithms for the problem, including a 4-approximation algorithm running in O(n log n log h) time, and a 3-approximation algorithm with O(nh log n+nh²) runtime, where h is the size of the convex hull of P. [ABSTRACT FROM AUTHOR]

In the separability problem of bichromatic point sets. given two sets of points colored as blue and red, we want to put a special geometric shape in a manner that includes the blue points while avoiding the red ones. This problem has various applications in data mining and other fields. Separability by various shapes, including L-shaped polygons. has been studied in the literature. In this paper. the separability of bichromatic point sets by C-shaped polygons, which are more general than L-shaped polygons, is studied and an 0(n log n)-time algorithm is presented. where n is the total number of points. [ABSTRACT FROM AUTHOR]

Urban villages represent informal residential areas emerging since China's rapid urbanization process. Scientific map generalization of urban villages with scientific maps aids readers in discerning their distribution and making informed decisions concerning them. However, there is still a scarcity of research on the automatic extraction and generalization of urban villages from vector data, which needs to be studied to further improve the expression of maps. To address this problem, this paper presents a methodology for the extraction and generalization of urban villages from Digital Line Graphics. Firstly, a heuristic approach is employed to analyze the atypical morphological characteristics of urban villages. Then, indices based on computational geometry and the modified Hausdorff distance are utilized to quantify these traits. Lastly, an automatic generalization principle for urban villages is offered. The approach was tested in experimental blocks and proved to be effective. It offers a novel method for the automatic extraction and cartography of urban villages. [ABSTRACT FROM AUTHOR]

Among the methods of 3D reconstruction, the automatic generation of 3D models from building documentation is one of the most accessible and inexpensive. For 30 years, researchers have proposed multiple methods to automatically generate 3D models from 2D drawings. This study compiles this research and discusses the different methods used to generate 3D models from 2D drawings. It offers a critical review of these methods, focusing on the coverage and completeness of the reconstruction process. This review allows us to identify the research gaps in the literature, and opportunities for improvement are identified for future research. [ABSTRACT FROM AUTHOR]

Among the methods of 3D reconstruction, the automatic generation of 3D models from building documentation is one of the most accessible and inexpensive. For 30 years, researchers have proposed multiple methods to automatically generate 3D models from 2D drawings. This study compiles this research and discusses the different methods used to generate 3D models from 2D drawings. It offers a critical review of these methods, focusing on the coverage and completeness of the reconstruction process. This review allows us to identify the research gaps in the literature, and opportunities for improvement are identified for future research.

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric (1−ε) –approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

As the need for handling complex geometries in computational fluid dynamics (CFD) grows, efficient and accurate mesh generation techniques become paramount. This study presents an adaptive mesh refinement (AMR) technology based on cell-based Cartesian grids, employing a distance-weighted least squares interpolation for finite difference discretization and utilizing immersed boundary methods for wall boundaries. This facilitates effective management of both transient and steady flow problems. Validation through supersonic flow over a forward-facing step, subsonic flow around a high Reynolds number NHLP airfoil, and supersonic flow past a sphere demonstrated AMR's efficacy in capturing essential flow characteristics while wisely refining and coarsening meshes, thus optimizing resource utilization without compromising accuracy. Importantly, AMR simplified the capture of complex flows, obviating manual mesh densification and significantly improving the efficiency and reliability of CFD simulations. [ABSTRACT FROM AUTHOR]

A new algorithm is presented for detecting the local weak reflection symmetries in raster images. It uses contours extracted from the segmented image. A convex hull is constructed on the contours, and so-called anchor points are placed on it. The bundles of symmetry line candidates are placed in these points. Each line splits the plane into two open half-planes and arranges the contours into three sets: the first contains the contours pierced by the considered line, while the second and the third include the contours located in one or the other half-plane. The contours are then checked for the reflection symmetry. This means looking for self-symmetries in the first set, and symmetric pairs with one contour in the second set and one contour in the third set. The line which is evaluated as the best symmetry line is selected. After that, the symmetric contours are removed from sets two and three. The remaining contours are then checked again for symmetry. A multi-branch tree representing the hierarchy of the detected local symmetries is the result of the algorithm. [ABSTRACT FROM AUTHOR]

We study the problem of perfect tiling in the plane and explore the possibility of tiling a rectangle using integral distinct squares. Assume a set of distinguishable squares (or equivalently a set of distinct natural numbers) is given, and one has to decide whether it can tile the plane or a rectangle or not. Previously, it has been proved that tiling the plane is not feasible using a set of odd numbers or an infinite sequence of natural numbers including exactly two odd numbers. The problem is open for different situations in which the number of odd numbers is arbitrary. In addition to providing a solution to this special case, we discuss some open problems to tile the plane and rectangles in this paper. [ABSTRACT FROM AUTHOR]

Geometry and topology are both central concepts in geospatial data modelling and management. While geometry is the central concept for computational geometry applications, e.g. to intersect surfaces and solids in 3D space, topology is helpful for many application classes starting from city modelling to subsurface modelling and indoor navigation. Furthermore, p-adic numbers are useful for describing hierarchical processes on topological models. In this paper we first shortly review geometry- and topology-based approaches used for geospatial applications. We then describe our approach on turning geometry "upside down" focusing on topology during the whole process of distributed geospatial computing, data modelling, data management, and simulation. Furthermore, the way to use p-adic numbers for the description of hierarchical processes on topological models is shown for the example of simulation and the idea of p-adic analysis in distributed simulations is presented in the context of topological city and building models. The approach opens new insights such as topological relationships, components, and efficiently studying of the approximate behaviour of processes in the built environment using distributed computational systems. Finally, exemplary applications are presented to underline the importance of this new approach. [ABSTRACT FROM AUTHOR]

Data quality is of crucial importance in the field of automated or digitally assisted assembly. This paper presents a comprehensive data set of triangle meshes representing electrical and electronic components obtained by scraping Computer Aided Design (CAD) models from the Internet. Consisting of a total of 234 triangle meshes with labelled vertices, this data set was specifically created for segmentation tasks. Its versatility for multimodal tasks is underscored by the presence of various labels, including vertex labels, categories, and subcategories. This paper presents the data set and provides a thorough statistical analysis, including measures of shape, size, distribution, and inter-rater reliability. In addition, the paper suggests several approaches for using the data set, considering its multimodal characteristics. The data set and related findings presented in this paper are intended to encourage further research and advancement in the field of manufacturing automation, specifically spatial assembly. [ABSTRACT FROM AUTHOR]

This groundbreaking research delves into the intricate molecular interactions between MXene and trihalomethanes (THs) through a comprehensive theoretical study employing density-functional theory (DFT). Trihalomethanes are common carcinogenic chlorination byproducts found in water sanitation systems. This study focuses on a pristine MXene [Mn+1·Xn] monolayer and its various terminal [Tx] functional groups [Mn+1·XnTx], strategically placed on the surface for enhanced performance. Our investigation involves a detailed analysis of the adsorption energies of THs on different MXene types, with the MXene-Cl layer emerging as the most compatible variant. This specific MXene-Cl layer exhibits remarkable properties, including a total dipole moment (TDM) of 12.443 Debye and a bandgap of 0.570 eV, achieved through meticulous geometry optimization and computational techniques. Notably, THs such as trichloromethane (CHCl3), bromide-chloromethane (CHBrCl2), and dibromochloromethane (CHBr2Cl) demonstrate the highest TDM values, indicating substantial changes in electronic and optical parameters, with TDM values of 16.363, 15.998, and 16.017 Debye, respectively. These findings highlight the potential of the MXene-Cl layer as an effective adsorbent and detector for CHF3, CHClF2, CHCl3, CHBrCl2, and CHBr2Cl. Additionally, we observe a proportional increase in the TDM and bandgap energy, indicative of conductivity, for various termination atom combinations, such as Mxene-O-OH, Mxene-O-F, Mxene-O-Cl, Mxene-OH-F, Mxene-F-Cl, and Mxene-OH-Cl, with bandgap energies measured at 0.734, 0.940, 1.120, 0.835, and 0.927 eV, respectively. Utilizing DFT, we elucidate the adsorption energies of THs on different MXene surfaces. Our results conclusively demonstrate the significant influence of the termination atom nature and quantity on MXene's primitive TDM value. This research contributes to our understanding of MXene–THs interactions, offering promising avenues for the development of efficient adsorbents and detectors for THs. Ultimately, these advancements hold the potential to revolutionize water sanitation practices and enhance environmental safety. [ABSTRACT FROM AUTHOR]

Partitioning two- or multidimensional polygons into rectangular and rectilinear components is a fundamental problem in computational geometry. Rectangular and rectilinear decomposition have multiple applications in various fields of arts as well as sciences, especially when dissecting information into smaller chunks for efficient analysis, manipulation, identification, storage, and retrieval is essential. This article presents three simple yet elegant solutions for splitting geometric shapes (particularly non-diagonal ones) into non-overlapping and rectangular sub-objects. Experimental results suggest that each proposed method can successfully divide n-dimensional rectilinear shapes, including those with holes, into rectangular components containing no background elements. The proposed methods underwent testing on a dataset of 13 binary images, each with 1 … 4 dimensions, and the most extensive image contained 4096 elements. The test session consisted of 5 runs where starting points for decomposition were randomized where applicable. In the worst case, two of the three methods could complete the task in under 40 ms, while this value for the third method was around 11 s. The success rate for all the algorithms was 100 %.

This paper addresses the problem of computing the optimal stacking of two monotone polytopes P and Q in Rd. A monotone polytope in Rd is defined as a polytope whose intersection with any line parallel to the last coordinate axis xd is connected, and the stacking of P and Q is defined as a translation of Q, such that “Q touches P from above”. To evaluate the stack, we use three different scoring criteria: (1) the height of the stack, (2) the maximum pointwise distance along the xd-axis, and (3) the volume between P and Q. We propose exact algorithms to compute the optimal stacking for each scoring criterion.

The Art Gallery Problem (AGP) is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k, the goal is to decide if there exists a setG of k guards within P such that every point p ∈ P is seen by at least one guard д ∈ G. Each guard corresponds to a point in the polygon P, and we say that a guard д sees a point p if the line segment pд is contained in P. We prove that the AGP is ∃R-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the AGP, and (2) the AGP is not in the complexity class NP unless NP = ∃R. As a corollary of our construction, we prove that for any real algebraic number α, there is an instance of the AGP where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set S ⊆ [0, 1]2, there exists a polygon with corners at rational coordinates such that for every p ∈ [0, 1]2, there is a set of guards of minimum cardinality containing p if and only if p ∈ S. In the ∃R-hardness proof for the AGP, we introduce a new ∃R-complete problem ETR-INV. We believe that this problem is of independent interest, as it has already been used to obtain ∃R-hardness proofs for other problems. [ABSTRACT FROM AUTHOR]

In this article, we study the intersection of a finite collection of disks in Euclidean space by examining spheres of various dimensions and their poles (extreme values with respect to canonical projections) contained within the intersection's boundary. We derive explicit formulae for computing these extreme values and present two applications. The first application involves computing the smallest common rescaling factor for the radii of the disk system, which brings the system to a single point of intersection. This calculation allows us to compute the generalized Čech filtration, a crucial tool for the topological data analysis of weighted point clouds. The second application focuses on determining the minimal Axis-Aligned Bounding Box (AABB) for the intersection of a finite collection of disks in Euclidean space, addressing a significant problem in computational geometry. We consider that this work aims to contribute to the fields of topological data analysis and computational geometry by providing new tools for analyzing complex geometric structures. [ABSTRACT FROM AUTHOR]

Metal-coated lattice structures hold significant promise for customizing mechanical properties in diverse industrial applications, including the mechanical arms of unmanned aerial vehicles. However, their intricate geometries pose computational challenges, resulting in time-intensive and costly numerical evaluations. This study introduces a parameterization-based multiscale method to analyze body-centered cubic lattice structures with metal coatings. We establish the validity and precision of our proposed method with a comparative analysis of numerical results at the Representative Volume Element (RVE) scale and experimental findings, specifically addressing both elastic tensile and bending stiffness. Furthermore, we showcase the method's accuracy in interpreting the bending stiffness of coated lattice structures using a homogenized material-based solid model, underscoring its effectiveness in predicting the elastic properties of such structures. In exploring the mechanical characterization of coated lattice structures, we unveil positive correlations between elastic tensile stiffness and both coating thickness and strut diameter. Additionally, the metal coating significantly enhances the structural elastic bending stiffness multiple times over. The diverse failure patterns observed in coated lattices under tensile and bending loads primarily stem from varied loading-induced stress states rather than external factors. This work not only mitigates computational challenges but also successfully bridges the gap between mesoscale RVE mechanical properties and those at the global structural scale. [ABSTRACT FROM AUTHOR]

Given a set of n disks in the plane, we study the problem of finding k lines that together intersect the maximum number of input disks. We consider three variants of this problem with the following constraints on the solution: (1) no constraint on the lines, (2) the k lines should be parallel and (3) the k lines should pass through a common point. For k = 2 , we give O (n 3 log n) -time algorithms for all three cases. For any fixed k ≥ 3 , we give an O (n 3 k / 2) -time algorithm for (1). For variants (2) and (3), the running times of our algorithms vary from O (n 4) to O (n 6) . [ABSTRACT FROM AUTHOR]

Geometric descriptions of deep neural networks (DNNs) have the potential to uncover core representational principles of computational models in neuroscience. Here we examined the geometry of DNN models of visual cortex by quantifying the latent dimensionality of their natural image representations. A popular view holds that optimal DNNs compress their representations onto low-dimensional subspaces to achieve invariance and robustness, which suggests that better models of visual cortex should have lower dimensional geometries. Surprisingly, we found a strong trend in the opposite direction—neural networks with high-dimensional image subspaces tended to have better generalization performance when predicting cortical responses to held-out stimuli in both monkey electrophysiology and human fMRI data. Moreover, we found that high dimensionality was associated with better performance when learning new categories of stimuli, suggesting that higher dimensional representations are better suited to generalize beyond their training domains. These findings suggest a general principle whereby high-dimensional geometry confers computational benefits to DNN models of visual cortex. Author summary: The effective dimensionality of neural population codes in both brains and artificial neural networks can be far smaller than the number of neurons in the population. In vision, it has been argued that there are crucial benefits of representing images using codes that are as simple and low-dimensional as possible, allowing representations to emphasize key semantic content and attenuate irrelevant perceptual details. However, there are competing benefits of high-dimensional codes, which can capture rich perceptual information to better support an open-ended set of visual behaviors. We quantified the effective dimensionality of neural networks created using a diverse set of training paradigms and compared these networks with image-evoked codes in the visual cortex of both monkeys and humans. Our findings revealed striking benefits of networks with higher effective dimensionality, which were consistently better predictors of cortical activity patterns and were able to readily learn new categories of images outside of their training domains. Together, these findings demonstrate the computational benefits of high-dimensional sensory codes, and they suggest that current neural network models of visual cortex may be better understood in terms of the richness of their representations rather than the details of their training tasks. [ABSTRACT FROM AUTHOR]

We show an upper bound of sin(3π/10 )/sin(2π/5 )−sin(3π/10 ) < 5.70 on the spanning ratio of Θ5-graphs, improving on the previous best known upper bound of 9.96 [Bose, Morin, van Renssen, and Verdonschot. The Theta-5-graph is a spanner. Computational Geometry, 2015. [ABSTRACT FROM AUTHOR]

A covering path for a planar point set is a path drawn in the plane with straight- line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let π(n) be the minimum number such that every set of n points in the plane can be covered by a noncrossing path with at most π(n) edges. Let T(n) be the analogous number for non-crossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: (5n)/9 - O(1) < π(n) < (1 - 1/601080391), n and (9n)/17 - O(1) < tau(n) ≤ [5n/6]. We report the following improved upper bounds: π(n) <= (1 - 1/22), n and t(n) ≤ =[(4n)/5]. In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let rho(k) be the minimum number such that every k-colored point set in the plane admits a perfect rainbow polygon of size p(k). Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that 20k / 19 - O(1) < p(k) < 10k/7+O(1) We report the improved upper bound p(k) < 7k/5 + O(1) To obtain the improved bounds we present simple algorithms that achieve paths, trees, and polygons with our desired number of edges. [ABSTRACT FROM AUTHOR]

Object retrieval systems measure the degree of similarity of the shape of 3D models. They search for the elements of the 3D model databases that resemble the query model. In structural bioinformatics, the query model is a protein tertiary/quaternary structure and the objective is to find similarly shaped molecules in the Protein Data Bank. With the ever-growing size of the PDB, a direct atomic coordinate comparison with all its members is impractical. To overcome this problem, the shape of the molecules can be encoded by fixed-length feature vectors. The distance of a protein to the entire PDB can be measured in this low-dimensional domain in linear time. The state-of-the-art approaches utilize Zernike–Canterakis moments for the shape encoding and supply the retrieval process with geometric data of the input structures. The BioZernike descriptors are a standard utility of the PDB since 2020. However, when trying to calculate the ZC moments locally, the issue of the deficiency of libraries readily available for use in custom programs (i.e., without relying on external binaries) is encountered, in particular programs written in Python. Here, a fast and well-documented Python implementation of the Pozo–Koehl algorithm is presented. In contrast to the more popular algorithm by Novotni and Klein, which is based on the voxelized volume, the PK algorithm produces ZC moments directly from the triangular surface meshes of 3D models. In particular, it can accept the molecular surfaces of proteins as its input. In the presented PK-Zernike library, owing to Numba's just-in-time compilation, a mesh with 50,000 facets is processed by a single thread in a second at the moment order 20. Since this is the first time the PK algorithm is used in structural bioinformatics, it is employed in a novel, simple, but efficient protein structure retrieval pipeline. The elimination of the outlying chain fragments via a fast PCA-based subroutine improves the discrimination ability, allowing for this pipeline to achieve an 0.961 area under the ROC curve in the BioZernike validation suite (0.997 for the assemblies). The correlation between the results of the proposed approach and of the 3D Surfer program attains values up to 0.99. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) contain coverage holes caused by both random node sensor deployment and malfunctioning nodes. Because fixing the battery is challenging, collaborative discovery and assessment of coverage shortfalls, as well as getting rid of these holes, has been recognized as critical in WSNs. While placing nodes for sensors in a large-scale WSN is challenging. This research provides a cost-effective coverage hole detection approach based on collaborative distributed point placement. Create a polygon first by employing an angle estimate approach and neighbor data. Following that, a based on points hole identification technique is used to assess if a coverage issue appears in a large-scale WSN's supplied ROI. Furthermore, the region of the coverage hole is estimated using computational geometry-based polygonal triangulation methods. The accuracy of the method is tested here using statistical data. The results show that it outperforms earlier coverage hole-detecting algorithms. In particular, the method improves coverage rate by 75% when compared to conventional methodologies. It also lowers energy usage by 90%, adding to increased network lifetime. The quantitative favourable results demonstrate the effectiveness of the collaborative distributed point placement technique in detecting and successfully resolving coverage gaps in WSNs. In regards to coverage rate, energy consumption, and network longevity, the system being proposed beats previous coverage hole-detecting techniques. [ABSTRACT FROM AUTHOR]

The tongue surface houses a range of papillae that are integral to the mechanics and chemistry of taste and textural sensation. Although gustatory function of papillae is well investigated, the uniqueness of papillae within and across individuals remains elusive. Here, we present the first machine learning framework on 3D microscopic scans of human papillae ( n = 2092 ), uncovering the uniqueness of geometric and topological features of papillae. The finer differences in shapes of papillae are investigated computationally based on a number of features derived from discrete differential geometry and computational topology. Interpretable machine learning techniques show that persistent homology features of the papillae shape are the most effective in predicting the biological variables. Models trained on these features with small volumes of data samples predict the type of papillae with an accuracy of 85%. The papillae type classification models can map the spatial arrangement of filiform and fungiform papillae on a surface. Remarkably, the papillae are found to be distinctive across individuals and an individual can be identified with an accuracy of 48% among the 15 participants from a single papillae. Collectively, this is the first evidence demonstrating that tongue papillae can serve as a unique identifier, and inspires a new research direction for food preferences and oral diagnostics. [ABSTRACT FROM AUTHOR]

Topic models provide a useful text-mining tool for learning, extracting, and discovering latent structures in large text corpora. Although a plethora of methods have been proposed for topic modeling, lacking in the literature is a formal theoretical investigation of the statistical identifiability and accuracy of latent topic estimation. In this article, we propose a maximum likelihood estimator (MLE) of latent topics based on a specific integrated likelihood that is naturally connected to the concept, in computational geometry, of volume minimization. Our theory introduces a new set of geometric conditions for topic model identifiability, conditions that are weaker than conventional separability conditions, which typically rely on the existence of pure topic documents or of anchor words. Weaker conditions allow a wider and thus potentially more fruitful investigation. We conduct finite-sample error analysis for the proposed estimator and discuss connections between our results and those of previous investigations. We conclude with empirical studies employing both simulated and real datasets. for this article are available online. [ABSTRACT FROM AUTHOR]

Recognizing vessel navigation patterns plays a vital role in understanding maritime traffic behaviors, managing and planning vessel activities, spotting outliers, and predicting traffic. However, the growth in trajectory data and the complexity of maritime traffic in recent years presents formidable challenges to this endeavor. Existing approaches predominantly adopt a 'trajectory perspective', where the instantaneous behaviors of vessel groups (e.g., the homing of fishing vessels) that occurred at certain times are concealed in the massive trajectories. To bridge this gap and to reveal collective patterns and behaviors, we look at vessel patterns and their dynamics at only individual points in time (snapshots). In particular, we propose a recognition framework from the snapshot perspective, mixing ingredients from group dynamics, computational geometry, graph theory, and visual perception theory. This framework encompasses algorithms for detecting basic types of patterns (e.g., collinear, curvilinear, and flow) and strategies to combine the results. Case studies were carried out using vessel trajectory (AIS) data around the Suez Canal and other areas. We show that the proposed methodology outperformed DBSCAN and clustering by measuring local direction centrality (CDC) in recognizing fine-grained vessel groups that exhibit more cohesive behaviors. Our results find interesting collective behaviors such as convoy, turning, avoidance, mooring (in open water), and berthing (in the dock), and also reveal abnormal behaviors. Such results can be used to better monitor, manage, understand, and predict maritime traffic and/or conditions. [ABSTRACT FROM AUTHOR]

Driven by the growing interest of the scientific community and the proliferation of research in this field, cranial implants have seen significant advancements in recent years regarding design techniques, structural optimisation, appropriate material selection and fixation system method. Custom implants not only enhance aesthetics and functionality, but are also crucial for achieving proper biological integration and optimal blood irrigation, critical aspects in bone regeneration and tissue health. This research aims to optimize the properties of implants designed from triply periodic minimal surface structures. The gyroid architecture is employed for its balance between mechanical and biological properties. Experimental samples were designed varying three parameters of the surface model: cell size, isovalue and shape factor. Computational simulation tools were used for determining the relationship between those parameters and the response variables: the surface area, permeability, porosity and Young modulus. These tools include computer aided design, finite element method and computational fluid dynamics. With the simulated values, the corresponding regression models were fitted. Using the NSGA-II, a multi-objective optimisation was carried out, finding the Pareto set which includes surface area and permeability as targets, and fulfil the constraints related with the porosity and Young modulus. From these non-dominated solutions, the most convenient for a given application was chosen, and an optimal implant was designed, from a patient computed tomography scan. An implant prototype was additively manufactured for validating the proposed approach.

Precise monitoring of individual crop growth and health status is crucial for precision agriculture practices. However, traditional inspection methods are time-consuming, labor-intensive, prone to human error, and may not provide the comprehensive coverage required for the detailed analysis of crop variability across an entire field. This research addresses the need for efficient and high-resolution crop monitoring by leveraging Unmanned Aerial Vehicle (UAV) imagery and advanced computational techniques. The primary goal was to develop a methodology for the precise identification, extraction, and monitoring of individual corn crops throughout their growth cycle. This involved integrating UAV-derived data with image processing, computational geometry, and machine learning techniques. Bi-weekly UAV imagery was captured at altitudes of 40 m and 70 m from 30 April to 11 August, covering the entire growth cycle of the corn crop from planting to harvest. A time-series Canopy Height Model (CHM) was generated by analyzing the differences between the Digital Terrain Model (DTM) and the Digital Surface Model (DSM) derived from the UAV data. To ensure the accuracy of the elevation data, the DSM was validated against Ground Control Points (GCPs), adhering to standard practices in remote sensing data verification. Local spatial analysis and image processing techniques were employed to determine the local maximum height of each crop. Subsequently, a Voronoi data model was developed to delineate individual crop canopies, successfully identifying 13,000 out of 13,050 corn crops in the study area. To enhance accuracy in canopy size delineation, vegetation indices were incorporated into the Voronoi model segmentation, refining the initial canopy area estimates by eliminating interference from soil and shadows. The proposed methodology enables the precise estimation and monitoring of crop canopy size, height, biomass reduction, lodging, and stunted growth over time by incorporating advanced image processing techniques and integrating metrics for quantitative assessment of fields. Additionally, machine learning models were employed to determine relationships between the canopy sizes, crop height, and normalized difference vegetation index, with Polynomial Regression recording an R-squared of 11% compared to other models. This work contributes to the scientific community by demonstrating the potential of integrating UAV technology, computational geometry, and machine learning for accurate and efficient crop monitoring at the individual plant level.

A Fano problem consists of enumerating linear spaces of a fixed dimension on a variety, generalizing the classical problem of 27 lines on a cubic surface. Those Fano problems with finitely many linear spaces have an associated Galois group that acts on these linear spaces and controls the complexity of computing them in suitable coordinates. These Galois groups were first defined and studied by Jordan, who in particular considered the problem of lines in P 3 on a cubic surface. Recently, Hashimoto and Kadets determined the Galois groups for a special family of Fano problems and showed that all other Fano problems have Galois group that contains the alternating group. A complete classification of Galois groups of Fano problems rests on the determination of these Galois groups. We use computational tools to prove that several Fano problems of moderate size have Galois group equal to the symmetric group, each of which were previously unknown. [ABSTRACT FROM AUTHOR]

In the mathematical discipline of computational geometry (CG), practical algorithms for resolving geometric input and output issues are designed, analyzed, and put into practice. It is sometimes used to refer to pattern recognition and to define the solid modeling methods for manipulating curves and surfaces. CG is a rich field encompassing theories to solve complex optimization problems, such as path planning for mobile robot systems and extension to distributed multi-robot systems. This brief review discusses the fundamentals of CG and its application in solving well-known automated path-planning problems in single- and multi-robot systems. We also discuss three winning algorithms from the CG-SHOP (Computational Geometry: Solving Hard Optimization Problems) 2021 competition to evidence the practicality of CG in multi-robotic systems. We also mention some open problems at the intersection of CG and robotics. This review provides insights into the potential use of CG in robotics and future research directions at their intersection. [ABSTRACT FROM AUTHOR]

In recent years, several algorithms with different time complexities have been proposed for the construction of greedy spanners. However, a not so apparently suitable algorithm with running time complexity , namely the FG algorithm, is proved to be practically the fastest algorithm known for this task. One of the common bottlenecks in the greedy spanner construction algorithms is their use of the shortest path search operation (usually using Dijkstra’s algorithm). In this paper, we propose some improvements to the FG algorithm in order to reduce the imposed costs of the shortest path search operation, and therefore to reduce the time required for the construction of greedy spanners. In the first improvement, we reduce the number of this operation calls and in the second one, we reduce the cost of each run of the operation. Experimental results show these improvements are able to significantly accelerate the construction of greedy spanners, compared to the other existing algorithms, especially when the stretch factor gets close to 1.

We propose a novel and efficient algorithm to model high-level topological structures of neuronal fibers. Tractography constructs complex neuronal fibers in three dimensions that exhibit the geometry of white matter pathways in the brain. However, most tractography analysis methods are time consuming and intractable. We develop a computational geometry-based tractography representation that aims to simplify the connectivity of white matter fibers. Given the trajectories of neuronal fiber pathways, we model the evolution of trajectories that encodes geometrically significant events and calculate their point correspondence in the 3D brain space. Trajectory inter-distance is used as a parameter to control the granularity of the model that allows local or global representation of the tractogram. Using diffusion MRI data from Alzheimer's patient study, we extract tractography features from our model for distinguishing the Alzheimer's subject from the normal control. Software implementation of our algorithm is available on GitHub (https://github.com/UCSB-VRL/ReebGraph.