Search

Objective. To develop a computational tool that converts biological images into geometries compatible with computational software dedicated to the Monte Carlo simulation of radiation transport (TOPAS), and subsequent biological tissue responses (CompuCell3D). The depiction of individual biological entities from segmentation images is essential in computational radiobiological modeling for two reasons: image pixels or voxels representing a biological structure, like a cell, should behave as a single entity when simulating biological processes, and the action of radiation in tissues is described by the association of biological endpoints to physical quantities, as radiation dose, scored the entire group of voxels assembling a cell. Approach. The tool is capable of cropping and resizing the images and performing clustering of image voxels to create independent entities (clusters) by assigning a unique identifier to these voxels conforming to the same cluster. The clustering algorithm is based on the adjacency of voxels with image values above an intensity threshold to others already assigned to a cluster. The performance of the tool to generate geometries that reproduced original images was evaluated by the dice similarity coefficient (DSC), and by the number of individual entities in both geometries. A set of tests consisting of segmentation images of cultured neuroblastoma cells, two cell nucleus populations, and the vasculature of a mouse brain were used. Main results. The DSC was 1.0 in all images, indicating that original and generated geometries were identical, and the number of individual entities in both geometries agreed, proving the ability of the tool to cluster voxels effectively following user-defined specifications. The potential of this tool in computational radiobiological modeling, was shown by evaluating the spatial distribution of DNA double-strand-breaks after microbeam irradiation in a segmentation image of a cell culture. Significance. This tool enables the use of realistic biological geometries in computational radiobiological studies. [ABSTRACT FROM AUTHOR]

ABSTRACT In this article, the idea of essential information‐based compression is extended to trilinear datasets. This basically boils down to identifying and labelling the essential rows (ERs), columns (ECs) and tubes (ETs) of such three‐dimensional datasets that allow by themselves to reconstruct in a linear way the entire space of the original measurements. ERs, ECs and ETs can be determined by exploiting convex geometry computational approaches such as convex hull or convex polytope estimations and can be used to generate a reduced version of the data at hand. These compressed data and their uncompressed counterpart share the same multilinear properties and their factorisation (carried out by means of, for example, parallel factor analysis–alternating least squares [PARAFAC‐ALS]) yield, in principle, indistinguishable results. More in detail, an algorithm for the assessment and extraction of the essential information encoded in trilinear data structures is here proposed. Its performance was evaluated in both real‐world and simulated scenarios which permitted to highlight the benefits that this novel data reduction strategy can bring in domains like multiway fluorescence spectroscopy and imaging. [ABSTRACT FROM AUTHOR]

The rigid matching of two geometric clouds is vital in the computer vision and its intelligent applications, such as computational geometry, robotics, shape modelling, surface reconstruction and mapping, and many other fields. The variants of the iterative closest point algorithm were employed as the most noticeable matching algorithm. In traditional ICP algorithms applications for symmetrical geometry matching, the initial uncertainty and the multiple local minima of the distance function adversely affect the alignment process, which leads to weak performance, such as incorrect correspondence, narrow convergence region, and instability. In this study, the novel algorithm fused the ICP algorithm, particle filter and K-means clustering to correctly estimate the transformation ICP parameters. Further guide to initial values of parameters and their covariance obtained by k-means clustering. Then, a particle filter was implemented to estimate accurate values and perform global optimization. In the introduced PF-ICP algorithm, the alignment parameters: rotation angles, scale factor, and translation, were defined as particles elements optimized using a sequential importance resampling (SIR) particle filter. The proposed algorithm was implemented on a medical robot FPGA board and applied to "three symmetrical models" and "noisy and poor datasets." The calculated variances and estimated parameters were compared with four modified ICP methods. The results show a significantly increasing accuracy and convergence region with an acceptable speed for the practical conditions. [ABSTRACT FROM AUTHOR]

We investigate algorithms for testing whether an image is connected. Given a proximity parameter ϵ ∈ (0 , 1) and query access to a black-and-white image represented by an n × n matrix of Boolean pixel values, a (1-sided error) connectedness tester accepts if the image is connected and rejects with probability at least 2/3 if the image is ϵ -far from connected. We show that connectedness can be tested nonadaptively with O (1 ϵ 2 ) queries and adaptively with O (1 ϵ 3 / 2 log 1 ϵ ) queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity O (1 ϵ 2 log 1 ϵ) and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make Ω (1 ϵ log 1 ϵ) queries. [ABSTRACT FROM AUTHOR]

Maintaining the maximum stiffness of components with as little material as possible is an overarching objective in computational design and engineering. It is well‐established that in stiffness‐optimal designs, material is aligned with orthogonal principal stress directions. In the limit of material volume, this alignment forms micro‐structures resembling quads or hexahedra. Achieving a globally consistent layout of such orthogonal micro‐structures presents a significant challenge, particularly in three‐dimensional settings. In this paper, we propose a novel geometric algorithm for compiling stress‐aligned hexahedral lattice structures. Our method involves deforming an input mesh under load to align the resulting stress field along an orthogonal basis. The deformed object is filled with a hexahedral grid, and the deformation is reverted to recover the original shape. The resulting stress‐aligned mesh is used as basis for a final hollowing procedure, generating a volume‐reduced stiff infill composed of hexahedral micro‐structures. We perform quantitative comparisons with structural optimization and hexahedral meshing approaches and demonstrate the superior mechanical performance of our designs with finite element simulation experiments. [ABSTRACT FROM AUTHOR]

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]

In deep functional maps, the regularizer computing the functional map is especially crucial for ensuring the global consistency of the computed pointwise map. As the regularizers integrated into deep learning should be differentiable, it is not trivial to incorporate informative axiomatic structural constraints into the deep functional map, such as the orientation‐preserving term. Although commonly used regularizers include the Laplacian‐commutativity term and the resolvent Laplacian commutativity term, these are limited to single‐scale analysis for capturing geometric information. To this end, we propose a novel and theoretically well‐justified regularizer commuting the functional map with the multiscale spectral manifold wavelet operator. This regularizer enhances the isometric constraints of the functional map and is conducive to providing it with better structural properties with multiscale analysis. Furthermore, we design an unsupervised deep functional map with the regularizer in a fully differentiable way. The quantitative and qualitative comparisons with several existing techniques on the (near‐)isometric and non‐isometric datasets show our method's superior accuracy and generalization capabilities. Additionally, we illustrate that our regularizer can be easily inserted into other functional map methods and improve their accuracy. [ABSTRACT FROM AUTHOR]

An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an O ~ (n m ω - 1) + O (N) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where ω denotes the matrix multiplication exponent and the O ~ (·) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in O (k 2 m G + k N) time, under edit distance, or O (k m G + k N) time, under Hamming distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for k = 1 , the existing algorithms run in Ω (m N) time in the worst case. In this paper we make progress in this direction. We show that 1-EDSM can be solved in O ((n m 2 + N) log m) or O (n m 3 + N) time under edit distance. For the decision version of the problem, we present a faster O (n m 2 log m + N log log m) -time algorithm. We also show that 1-EDSM can be solved in O (n m 2 + N log m) time under Hamming distance. Our algorithms for edit distance rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or 2d range emptiness), which we show how to solve efficiently. In order to obtain an even faster algorithm for Hamming distance, we rely on employing and adapting the k-errata trees for indexing with errors [Cole et al., STOC 2004]. This is an extended version of a paper presented at LATIN 2022. [ABSTRACT FROM AUTHOR]

Sequential sampling methods are often used to estimate functions describing models subjected to time‐intensive simulations or expensive experiments. These methods provide guidelines for point selection in the domain to capture maximum information about the function. However, in most sequential sampling methods, determining a new point is a time‐consuming process. In this paper, we propose a new method, named Sieve, to sequentially select points of an initially unknown function based on the definition of proper intervals. In contrast with existing methods, Sieve does not involve function estimation at each iteration. Therefore, it presents a greater computational efficiency for achieving a given accuracy in estimation. Sieve brings in tools from computational geometry to subdivide regions of the domain efficiently. Further, we validate our proposed method through numerical simulations and two case studies on the calibration of internal combustion engines and the optimal exploration of an unknown environment by a mobile robot. [ABSTRACT FROM AUTHOR]

By considering maps and routes as sequences of line segments, their intersections can be computed to find out useful information like the possibility of collision in a military area where the parties do not trust each other. At the first glance, finding the coordinates of the intersections is seemed impossible to be solved securely since having coordinates of two intersection points on the same line reveals the passing line. In this paper, we solve this problem by suggesting a secure two-party protocol in presence of passive adversaries. Additionally, regarding the fact that in some cases, the fixedness of the inputs of the parties in classic security models is an unrealistic assumption, we define the new concept of input-adaptive security and show that our method is secure against such an adversary who is able to select his inputs adaptively. In addition to serve different approaches like oblivious transfer and sometimes homomorphic encryption, we also employ some tricks to prevent the distribution of harmful information between specific parties to achieve our intended security level. We provide formal proofs to show the security of our protocol. Time complexity analysis and implementations show that our protocol finds the intersections in feasible time of O (n log n) and indicate that our protocol is as good as the unsecure optimal method of line segment intersection computation. In comparison, previous methods require O (n 2) to only detect the existence of intersection between two sets of n line segments and are unable to find the coordinates of the intersections. [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]

We show that the gradient of a strongly differentiable function at a point is the limit of a single coordinate‐free Clifford quotient between a multidifference pseudo‐vector and a pseudo‐scalar, or of a sum of Clifford quotients between scalars (as numerators) and vectors (as denominators), both evaluated at the vertices of a same non‐degenerate simplex contracting to that point. Such result allows to fix an issue with a defective definition of pseudo‐scalar field in Sobczyck's simplicial calculus. Then, we provide some consequences and conjectures implied by the foregoing results. [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 h pairwise disjoint convex polygonal obstacles in the plane, defined with n vertices, we preprocess and compute one routing table at each vertex in a subset of vertices of . For routing a packet from any vertex s ∈ to any vertex t ∈ , our scheme computes a routing path with a multiplicative stretch 1 + and an additive stretch 2 k ℓ , by consulting routing tables at only a subset of vertices along that path. Here, k is the number of obstacles of the routing path intersects, and ℓ depends on the geometry of obstacles in . During the preprocessing phase, we construct routing tables of size O (n + h 3 2 polylog (h )) in O (n + h 3 2 polylog (h )) time, where < 1 is an input parameter. [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 image processing, computer vision algorithms are applied to regions bounded by closed contours. These contours are often irregular, poorly defined, and contain holes or unavailable areas inside. A common problem in computational geometry includes finding the k-sided polygon (k-gon) of maximum area or maximum perimeter inscribed within a contour. This paper presents a generic method to obtain user-defined polygons within a region. Users can specify the number k of sides of the polygon to obtain. Additionally, users can also decide whether the calculated polygon should be the largest in area or perimeter. This algorithm produces a polygon or set of polygons that can be used to segment an image, allowing only relevant areas to be processed. In a real-world application, the validity and versatility of the proposed method are demonstrated. In addition, the source code developed in Java and Python is available in a GitHub repository so that researchers can use it freely. [ABSTRACT FROM AUTHOR]

Auxetic textiles are intriguing materials with unusual capabilities. These materials exhibit a negative Poisson's ratio with extraordinary performance in toughness, resilience, shear resistance, and acoustic properties mainly due to their special structure and associated deformation mechanics. Auxetic materials can also have applications around energy absorption and can effectively be used for vibration damping and shock absorbency. The exceptional behaviour of auxetic textiles can be obtained by utilising specific fibrous materials and introducing auxetic geometry and structures differently during weaving, knitting, and nonwoven manufacturing. This issue of Textile Progress highlights the fundamental aspects of various auxetic structures and their properties in general and a detailed analysis of auxetic textile structures and composites, their manufacturing processes, modelling, characterisation, and applications. These materials can potentially revolutionise their applications in sports, automotive, construction industry, biomedical engineering, aerospace, marine, and defence personal protective equipment. Fundamental understanding of auxetic geometry, followed by developing and analysing these geometries by analytical and computational modelling, translating the geometry into appropriate textile structures for actual fabric production, characterisation of auxetic fabrics and their composites, and finally, some innovative applications in technical textiles are some of the fascinating issues addressed in this review. [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.

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack n + k disks. Thus the problem of packing equal disks is the special case of our problem with n = h = 0 . While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for h = 0 . Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h + k) O (h + k) · | I | O (1) , where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h. [ABSTRACT FROM AUTHOR]

The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min – the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear-time algorithms. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise. [ABSTRACT FROM AUTHOR]

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]

Persistent homology barcodes and diagrams are a cornerstone of topological data analysis that capture the "shape" of a wide range of complex data structures, such as point clouds, networks, and functions. However, their use in statistical settings is challenging due to their complex geometric structure. In this paper, we revisit the persistent homology rank function, which is mathematically equivalent to a barcode and persistence diagram, as a tool for statistics and machine learning. Rank functions, being functions, enable the direct application of the statistical theory of functional data analysis (FDA)—a domain of statistics adapted for data in the form of functions. A key challenge they present over barcodes in practice, however, is their lack of stability—a property that is crucial to validate their use as a faithful representation of the data and therefore a viable summary statistic. In this paper, we fill this gap by deriving two stability results for persistent homology rank functions under a suitable metric for FDA integration. We then study the performance of rank functions in functional inferential statistics and machine learning on real data applications, in both single and multiparameter persistent homology. We find that the use of persistent homology captured by rank functions offers a clear improvement over existing non‐persistence‐based approaches. [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]

In this work, we introduce a new approach for computing Delaunay triangulations. Delaunay triangulations have numerous applications in geolocation, communications and other ICT systems or practical applications. Having available various types of approaches for computing such structures is rather desired from an implementation and computational point of view. We adopt Genetic Algorithms for computing Delaunay triangulations and present the design and evaluation of our novel approach. We consider a set of points in the plane as vertices and connect them with edges, creating the point graph. We have developed in C++ an application framework based on genetic algorithms, called Delaunay_Genetic, which produces the Delaunay triangulation structure of a given set of points in the plane. Delaunay_Genetic considers a novel graph-based chromosome representation of desired solutions, creates an initial population of individuals (chromosomes), an initial generation, and produces from the original population (generation) new generations of individuals in each repetition of the genetic process of Reproduction. Each new generation emerges more robust than the previous one. Our evaluations have revealed that the Delaunay triangulation yielded by Delaunay_Genetic, achieves an accuracy of 98–100% of the optimal Delaunay triangulation, while maintaining good convergence speed. Despite its limitations in computational time and space, the proposed novel approach exhibits several complementary benefits to computational geometry based approaches, such as allowing the insertion of new points in the triangulation dynamically, leading to seamless adaptation to new conditions, parallelization of the computational process and tolerance to noise regarding the coordinates of the points. Therefore, this work provides a useful alternative approach for computing Delaunay triangulations. [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]

Three-dimensional (3D) geographic information systems (GIS) are vital for urban planning and architectural design, enabling detailed visualization and analysis of urban landscapes. However, the growing size of 3D city data and the transition to web environments cause performance challenges for real-time applications. This study addresses the need for optimizing 3D spatial analyses for the web using Quadtree data structures and multiprocessing tools. Optimization scenarios based on data size and hardware configurations are evaluated, and the best hosting plans for GIS applications on cloud services are also considered. [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]

In this paper, we study the following Minimum Cost Multicovering (MCMC) problem: Given a set of n client points C and a set of m server points S in a fixed dimensional Rd space, determine a set of disks centered at these server points so that each client point c is covered by at least k(c) disks and the total cost of these disks is minimized, where k(·) is a function that maps every client point to some nonnegative integer no more than m and the cost of each disk is measured by the \alpha th power of its radius for some constant α >0. MCMC is a fundamental optimization problem with applications in many areas such as wireless/sensor networking. Despite extensive research on this problem for about two decades, only constant approximations were known for general k. It has been a long standing open problem to determine whether a PTAS is possible. In this paper, we give an affirmative answer to this question by presenting the first PTAS for it. Our approach is based on a number of novel techniques, such as balanced recursive realization and bubble charging, and new counterintuitive insights to the problem. Particularly, we approximate each disk with a set of sub-boxes and optimize them at the subdisk level. This allows us to first compute an approximate disk cover through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. [ABSTRACT FROM AUTHOR]

Object‐space occluding contours of triangular meshes (a.k.a. mesh contours) are at the core of many methods in computer graphics and computational geometry. A number of hierarchical data‐structures have been proposed to accelerate their computation on the CPU, but they do not map well to the GPU for real‐time applications, such as video games. We show that a simple, flat data‐structure composed of patches bounded by a normal cone and a bounding sphere may reach this goal, provided it is constructed to maximize the probability for a patch to be culled over all viewpoints. We derive a heuristic metric to efficiently estimate this probability, and present a greedy, bottom‐up algorithm that constructs patches by grouping mesh edges according to this metric. In addition, we propose an effective way of computing their bounding sphere. We demonstrate through extensive experiments that this data‐structure achieves similar performance as the state‐of‐the‐art on the CPU but is also perfectly adapted to the GPU, leading to up to ×5 speedups. [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]

The design representations of lattice structures are fundamental to the development of computational design approaches. Current applications of lattice structures are characterized by ever-growing demand on computational resources to solve difficult optimization problems or generate large datasets, opting for the development of efficient design representations which offer a high range of possible design variants, while at the same time generating design spaces with attributes suitable for computational methods to explore. In response, the focus of this work is to propose a parametric design representation based on crystallographic symmetries and investigate its implications for the computational design of lattice structures. The work defines design rules to support the design of functionally graded structures using crystallographic symmetries such that the connectivity between individual members in a structure with varying geometry is guaranteed and investigates how to use the parametrization in the context of optimization. The results show that the proposed parametrization achieves a compact design representation to benefit the computational design process by employing a small number of design variables to control a broad range of complex geometries. The results also show that the design spaces based on the proposed parametrization can be successfully explored using a direct search-based method. [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]

In the prize‐collecting geometric enclosure problem (PCGEP), a set S$S$ of points in the plane is given, each with an associated benefit. The goal is to find a simple polygon P$\mathcal {P}$ with vertices in S$S$ that maximizes the sum of the benefits of the points of S$S$ enclosed by P$\mathcal {P}$ minus the perimeter of P$\mathcal {P}$ multiplied by a given nonnegative cost. The PCGEP is NP‐complete and has applications to land surveying for exploration or preservation of natural resources. In this paper, we develop the first heuristic, called PCGEP‐GR, for the PCGEP and revisit a previously proposed integer linear programming (ILP) model to solve it to optimality. We conducted a comprehensive experimental study of that heuristic and an exact algorithm based on the ILP model. We show that a new set of constraints, together with the previous set, is necessary to guarantee the correctness of the ILP model and introduce preprocessing strategies that allow us to prove optimality 40% faster on average. The proposed heuristic is able to reach the optimum in 32% of our benchmark instances and, for those with unknown optima, PCGEP‐GR was found better than or at least as good solutions as the ones obtained by the cplex ILP solver in 54% of the cases. Notwithstanding these positive results, the design of effective heuristics for the PCGEP proved to be very challenging, which also led us to obtain a result that provides the theoretical foundation for future advances in the study of this problem. [ABSTRACT FROM AUTHOR]

We investigate how the complexity of Euclidean TSP for point sets P inside the strip (- ∞ , + ∞) × [ 0 , δ ] depends on the strip width δ . We obtain two main results. For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O (n log 2 n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2 2 , a bound which is best possible. We present an algorithm that is fixed-parameter tractable with respect to δ . Our algorithm has running time 2 O (δ) n + O (δ 2 n 2) for sparse point sets, where each 1 × δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [ 0 , n ] × [ 0 , δ ] , it has an expected running time of 2 O (δ) n . These results generalise to point sets P inside a hypercylinder of width δ . In this case, the factors 2 O (δ) become 2 O (δ 1 - 1 / d) . [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]

The finite-length rotating column has been extensively studied because of its importance in various fields, such as marine and aerospace. In this study, the hydrodynamic performance of a finite-length rotating column with two free ends at different angles of attack is investigated using a large eddy simulation method. The effects of various geometries (including an equal-section cylinder and a variable-section truncated cone), incoming flow velocities, column rotation speeds, and angles of attack on the lift and drag characteristics and wake field of the rotating column are analyzed. The results reveal that a free end creates a concentrated tip vortex, which shortens the effective length that can generate the Magnus effect. Across different geometries and computational conditions, a relatively consistent lift coefficient is found for angles of attack from 60° to 120°, with the cone design significantly reducing the drag by approximately 10% for angles of attack from 120° to 150°. These findings provide valuable insights into the practical application of finite-length rotating columns. Specific recommendations for optimizing the design of these columns are suggested, including choosing appropriate geometries and considering the effects of incoming flow velocities and column rotation speeds. [ABSTRACT FROM AUTHOR]

We propose conditioning field initialization for neural network-based topology optimization. In this work, we focus on (1) improving upon existing neural network-based topology optimization and (2) demonstrating that using a prior initial field on the unoptimized domain, the efficiency of neural network-based topology optimization can be further improved. Our approach consists of a topology neural network that is trained on a case by case basis to represent the geometry for a single topology optimization problem. It takes in domain coordinates as input to represent the density at each coordinate where the topology is represented by a continuous density field. The displacement is solved through a finite element solver. We employ the strain energy field calculated on the initial design domain as an additional conditioning field input to the neural network throughout the optimization. Running the same number of iterations, our method converges to a lower compliance. To reach the same compliance, our method takes fewer iterations. The addition of the strain energy field input improves the convergence speed compared to standalone neural network-based topology optimization. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Ordnance Equipment Engineering is the property of Chongqing University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The modeling capabilities of trigonometric B-spline curves with form parameters are comparable to those of classical B-spline curves in terms of their significance and use. Through the application of basic functions and shape parameters, this method presents the cubic trigonometric B-spline curves. Constructed by these functions, the concept of designing curves and surfaces possesses all the ideal geometric qualities, such as the partition of unity, convex hull, affine invariance, and variation decreasing. The parameters that are used in the creation of the recommended approach are helpful for several important form characteristics. These vital form aspects include local, global, and biased tension qualities, which provide good control over the curve and allow for shape change as required. In addition, the C 2 strategy is the one that is suggested for use. [ABSTRACT FROM AUTHOR]