# Tagged Questions

The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.

0answers
11 views

### Compute spatial second derivatives in Isogeometric analysis

Motivation: In isogeometric analysis, state variables(e.g. displacement) are defined in the parametric domain, which can be mapped to the physical domain by $\boldsymbol{\xi}\mapsto \boldsymbol{x}$ ...
1answer
48 views

### Fastest method for evaluating the limit of the sign of a polynomial

Consider a multivariate polynomial $f(x) = f(x_1, \ldots, x_n)$ with maximum degree $d$. Following the linear symbolic perturbation scheme described in Seidel 1998, I want to evaluate the limit ...
2answers
49 views

### Library for closest point on a polyhedron

I need to compute a closest point on a nonconvex polyhedron to a given point in 3D space. I need a simple algorithm or library. I search in CGAL but did not find a suitable function and the package is ...
3answers
104 views

### Closest interior point on integer grid to a vertex of a convex polyhedron

I have a 3 dimensional convex polyhedron whose vertex coordinates are rational. For one of these vertices, I would like to find the nearest integer grid point (under the Euclidean metric) that is ...
0answers
43 views

### Dissipation and symplectic manifolds

I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
1answer
121 views

### How to calculate the area of intersection between a 3D volume and a 2D plane

Hello if anyone can offer insight on how to solve my problem that would be great! I am looking to calculate the area of intersection between a 3D volume and a 2D plane. 3D volume: defined by 6 points ...
1answer
74 views

### How to treat hexahedral element with shifted hanging node?

When using the Hexpress grid generator one gets hexahedral cells, possibly with hanging nodes. Because of a smoothing step, the hanging nodes can be shifted: they are not necessarily on the straight ...
3answers
105 views

### Backward stable projection and normalization of a vector

Given a machine precision unit vector $n$, and an arbitrary vector $v$, I want an unconditionally backward stable method to compute $$f(v) = \frac{v-nn'v}{\left|v-nn'v\right|}$$ In other words, ...
0answers
36 views

### exact area resampling

I do image processing, and right now I need to resample some images taken from slightly different perspectives so I can match up features. The pixel intensities have scientific significance, so I want ...
1answer
37 views

### Error in Maple's CellDecomposition Command

I have a simple system that I want to process with the CellDecomposition command of Maple. I don't know why Maple is giving an error here! The code is ...
0answers
44 views

### Conservative field mapping between two topologically disconnected surface meshes

Some background: the Front-Tracking method uses a triangular surface mesh to describe the boundary between two immiscible fluids. To deal with the breakup and coalescence of the fluid interface, ...
2answers
105 views

### Restrict Voronoï diagram to a polygon

I managed to build the Voronoï diagram of n points using Fortune's algorithm. This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point). I'd like to ...
1answer
74 views

### Ray casting algorithm for multiple disjoint polygons is still valid?

We're dealing with country borders, that is the set of multiple disjoint domains that is made of polygons. To extract the different point on the map by a given country we've been said to implement ...
1answer
83 views

### Recovering coordinates by eigendecomposition without double-centering

Suppose an Euclidean distance $D\in\mathbb{R}^{n\times n}$ matrix between a set of $n$ objects is given. To obtain inner-products (which will be further be used to recover coordinates), entries of $D$ ...
1answer
738 views

### Concave polygon 'hull' finding

I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the ...
1answer
63 views

### Random placement of euclidean points with constrained inter-point distances in a fixed area

I'd like to place as many random points as possible in a 2D square $S=[0,1]x[0,1]$ such that the euclidean distance $d$ between any two points $d$ is greater than a given value $b$ (b is small). I'm ...
0answers
26 views

### Where can I find a detailed description of the AABBtree data structure implementation?

googling does not return much results on this. Are there any good descriptions in some book/article somewhere? I require a fast collision detection algorithm between two sets of unordered Axis ...
0answers
83 views

### What is the best C++ library for a AABBtree data structure?

what are your experiences with collision detection libraries that utilise AABBtrees, written in the C++ language? Cann you recommend one that is easy to use and communicates easily to other libraries? ...
2answers
106 views

### Is there an algorithm to find an almost-convex hull given a tolerance angle?

I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...
1answer
95 views

### Convex polytope volume and centroid calculation

I have troubles imagining how to compute a volume and centroid of an n-dimesional convex polytope. For a polygon (especially for convex polygon) the area and centroid are described in (wiki) by  ...
3answers
107 views

### How can I detect which among N bodies with different velocities will collide?

Suppose I have N different airplanes traveling on a two dimensional rectangular plane of size 400km x 400km (i.e. it is as if all planes travel at the same altitude). Assume each airplane has a ...
2answers
53 views

### Is there a special algorithm for computing the convex hull ordering when the candidate points are on the hull?

I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ...
2answers
81 views

### A sufficient number of distances to recover relative positions of n points

On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space. For instance, work from ...
0answers
60 views

### PRE-Requisites for Computational Mathematics [closed]

I have been searching the net for a few days as to what all courses i must have done to make sense of the field of Computational Mathematics. I came up with these: 1.) Discrete Mathematics and Data ...
3answers
471 views

### Finding which triangles points are in

Suppose I have a 2D mesh consisting of nonoverlapping triangles $\{T_k\}_{k=1}^N$, and a set of points $\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$. What is the best way to determine which triangle each ...
0answers
62 views

### Anisotropic cover with n-cuboids

I'm working on an algorithm for which I would like to cover an $n$-dimensional unit cube by a set of $n$-cuboids (i.e., $n$-dimensional rectangles). The size and orientation of these cuboids is ...
1answer
153 views

### Application of an orthogonal matrix to a 3D configuration of point

Suppose a 3D configuration of points is given, $X\in\mathbb{R}^{n\times 3}$, and a matrix $Q\in\mathbb{3\times 2}$, with orthonormal columns. Now, suppose a mapping to 2D is obtained as $$Y=XQ.$$ ...
1answer
580 views

### How to get all intersections between two simple polygons in O(n+k)

Basically the formulation of the problem I'd like to solve is very simple. Given 2 simple polygons (without self-intersections) report all intersecting edge pairs in O(n+k) time, where n - is a total ...
2answers
810 views

### Fastest Delaunay triangulation libraries for sets of 3D points

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
3answers
135 views

### Converting from planar polynomial domain to planar polygon

Let's assume we have a planar domain whose boundary can be described with a polynomial curve (like Bezier curves). Now assume that you want to produce a discretization of the boundary, i.e. you want ...
4answers
192 views

### How to create a random 3D domain representing a plant's root structure?

I would like to model laminar flow of water from roots to the stem of a plant. At the very end of the roots, the tubes vary from millimeter to centimeter scale in diameter and length. As we get closer ...
3answers
183 views

### Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices ...
1answer
51 views

### 2D Jacobi line maintenance?

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
4answers
255 views

### Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
0answers
147 views

### Why is my lower convex hull extraction algorithm not working?

Recently, I wrote an algorithm to obtain a delaunay triangulation of a random point set in $I=[-10,10]$x$[-10,10] \subset R^2$ by projecting these points onto the 3 dimensional paraboloid $z=x^2+y^2$, ...
1answer
301 views

### Sort a cloud of points with respect to an unstructured mesh of hexahedral cells

Question How would you sort a cloud of points with respect to an unstructured mesh of hexahedral cells? Each cell has a centre and a unique label to represent it. There are two cloud points ...
1answer
103 views

### Given values on a mesh, what algorithm can I use to construct efficiently level set contours?

I have a mesh, faces $F$, edges $E$, and vertices $V$, and I have a list of predefined level set contours. What algorithm can I use to construct contours in the most efficient manner? A plot of ...
2answers
344 views

### Is there any 2D shape repository?

As far as I see, there are many repositories for 3D shapes. But in FEM and many other applications, a planar mesh domain is also very common. However, I did not find a mesh repository specially ...
2answers
279 views

### Shape regularity in higher dimensions

In Finite Element theory, and other methods in scientific computing for PDEs, one uses meshes which fulfill several regularity criteria, many of them being equivalent. It is of interest to have ...
1answer
250 views

### How to efficiently determine the intersection of a vertical cutting plane with a mesh

I have a list of vertical cut planes, and I have a polygonal mesh ( it's a 2D+0.5D mesh, something like a 2D mesh with an extra dimension, $z$ attached to each point). One can assume that the mesh ...
5answers
661 views

### How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other?

I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear ...
1answer
141 views

### What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?

I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh ...
2answers
1k views

### Unstructured quad mesh-generation?

What is the best (scalability and efficiency) algorithms for generating unstructured quad meshes in 2D? Where can I find a good unstructured quad mesh-generator? (open-source preferred)
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 36, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9130470752716064, "perplexity_flag": "middle"}