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

learn more… | top users | synonyms

2
votes
1answer
131 views

Comparison of convex hulls [closed]

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; ...
0
votes
0answers
5 views

How to choose GPS setup? [migrated]

I need some advice on choosing a GPS setup to map estuarine habitats in the field. Our SA estuaries are often very narrow (1 to 2 km wide) and habitats are small. We distinguish between supratidal ...
1
vote
3answers
95 views

Point inside curved finite element

I like to create interpolation functions for second order finite element meshes. For elements with straight edges all is good, but some of my elements may be curved edges as shown in the figure: I ...
1
vote
3answers
92 views

Distance between points

I am wondering how can I solve following problem. Arrange randomly $n$ points inside a square of side $a$ under the condition that the distance between any two points may not be smaller than 1. I ...
2
votes
1answer
83 views

Monte Carlo Double Integration Implementation

Am implementing a monte carlo integration routine to compute this double integral in eqn 0.3 of page 2 of this paper 'Mobius energy of knots and unknots', Annals of Mathematics, ...
5
votes
2answers
127 views

Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
1
vote
2answers
44 views

Wrapping grid of points around curvature of an infinitely long cylinder [closed]

I have an infinitely long cylinder defined using radius a point in 3d Axis defined using a 3d vector I have a set of points with 3d coordinates placed in a grid. I want to wrap this grid of ...
1
vote
2answers
128 views

Ideas on how to search nearby geospatial data fast

I am looking at a very simple problem, but can't quite find the best solution. I need to accept a lat/lon coordinate and based on that coordinate find all the points within roughly ~1km (accuracy is ...
0
votes
0answers
53 views

Bijection between polyhedrals

Does there exist a bijection between a general axis-parallel polytope in $\mathbb{R}^n$ and a polytope embedded in a unit hypercube in $\mathbb{R}^n$? This means that the bijection must preserve the ...
3
votes
0answers
49 views

How to sample points in hyperbolic space?

Hyperbolic space in the Poincaré upper half space model looks like ordinary $\Bbb R^n$ but with the notion of angle and distance distorted in a relatively simple way. In Euclidean space I can sample a ...
3
votes
0answers
53 views

Shape measure for C-shaped objects

There are many well defined measures for many basic geometrical objects such as rectangularity (area coverage of minimum bounding rectangle), triangularity (area coverage of minimum enclosing ...
1
vote
1answer
59 views

Find area of a polygon. In C and Obj C.

I've been given an assignment: Create a console application (using C and Obj C) that will calculate area of a random polygon. The application should process input data as a .txt file with a list of ...
4
votes
1answer
49 views

Estimating the local compression/expansion ratio for a transformation on a point cloud

Let's say we have an unorganized point cloud P1 with N points, each with coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. ...
5
votes
2answers
191 views

applications of computational geometry in fields such as CFD?

Out of curiosity, I was recently trying to search what skills are required to be successful as developer in scientific computing field (e.g. CFD or similar). And to do so, I was going to through ...
2
votes
0answers
33 views

interpolate the circle going through three points using splines

It is known from Geometry that any 3 points determine a circle. This is the problem of Appolonius Programming solutions try to approximate using Bezier curves. Can you not draw conics as Bezier ...
1
vote
0answers
87 views

Equilateral triangle based mesh generation by intersection

In work I am currently working on I need to mesh some structure with equilateral triangles to study it using a kind of discrete element method known as spring networks or Lattice model. To mesh the ...
0
votes
2answers
73 views

Minimizing the edge length of a polygon preserving its angles

I am trying to minimize the edge lengths of a polygon while keeping the angles the same. I can achieve this geometrically (iteratively), however, I am looking for some related papers that can solve ...
0
votes
1answer
47 views

Exit point of a ray shot through the earth from another location on the earth?

I have a little computational geometry project I'm struggling with for a non-commercial "art" installation. It is driving me crazy and I'd happily pay for an implementable algorithm/solution ...
2
votes
0answers
44 views

Bracket Algebra, Straightening Algorithm

My apologies if the question is simple. I need to write a code for straightening algorithm. Which includes defining bracket algebra. I tried to write it in CoCoA-5, but it wasn't possible because ...
3
votes
1answer
71 views

How to Check a Hyper-Cube for Defects

I would greatly appreciate some help/references on solving the following problem: You are in charge of searching through a n-dimensional hyper-cube $[0,1]^n$ to make sure that it does not contain ...
0
votes
0answers
90 views

Help with the definition of constraints for a joint optimization problem

A trajectory is piecewise defined by the following polynomial form: $$ f(t) = a + bt+ct^{2}+dt^{3}+et^{4}+ft^{5}+gt^{6}+ht^{7}+it^{8}+jt^{9} $$ for every single segment composing the trajectory (the ...
0
votes
3answers
94 views

Meshing of polygons

I need to generate a sequence of increasingly denser high-quality triangular meshes for some pentagons in MATLAB. I want to supply as my input The coordinates of the 5 vertices of the pentagon ...
0
votes
1answer
105 views

Convex Polygon Intersection

Determining the intersection of two convex polygons is one of the fundamental problems in computational geometry . I'm asking for an algorithm having: INPUT: Given two convex polygons P and Q in 2D ...
1
vote
2answers
85 views

How to determine the support/influence domain for irregularly distributed nodes in the Element-Free Galekin Method?

EDIT (26-12-14):In the Belytschko's EFG code, the domain of influence for uniform distributed node can be calculated using the code below; my question is how to calculate xspac and yspac when the ...
1
vote
2answers
449 views

Determine unit outward normal vector for a curve

It is necessary for me to find the unit outward normal vector for the curve: $$\gamma=(x(t),y(t)) $$ where $$x(t)=\cos(t)−0.5\cos(3t)$$ and $$y(t)=\sin(t)+\sin(7t)+\sin(3t)$$ I know how to find ...
3
votes
2answers
160 views

How to determine a node is outside or inside a curve

Let $$x=0.5\cos(t)-0.3\cos(3t)$$ $$y=1.2+0.6\sin(t)-0.07\sin(3t)+0.2\sin(7t)$$ How could I know an arbitrary point is inside or outside of this curve? Also, another ...
0
votes
0answers
44 views

Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
3
votes
1answer
61 views

Riemann surfaces: computing $f(z) = \int_0^z \frac{dx}{\sqrt{P(x)}}$

I am trying to validate that the Schwartz-Christoffel mapping does indeed take the upper-half plane $\mathbb{H} = \{ z: \mathrm{Re}(z) > 0\}$ to a polygon. This involves integrals of functions ...
3
votes
1answer
66 views

Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
2
votes
2answers
99 views

Finding nearest neighbors using Jaccard distance for positive, real-valued vectors

Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance $d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$ to find ...
6
votes
2answers
401 views

A method to determine whether a point can be contained within a circle with no neighbouring points

I have been working on a particularly challenging problem and was hoping for some guidance. Here is my problem. I have a point cloud containing millions of points. For each point in the set, I need to ...
2
votes
1answer
164 views

What is the exact formulation of compressible Euler equation of gas dynamics in polar coordinates with artificial diffusion in 2D?

The interested equation is advection-diffusion equation. One of the canonical example is Navier-Stokes equations. However, I would like to let the coefficient of diffusion constant goes to zero, ...
2
votes
1answer
267 views

Translate a 3D point along a heading

I need to translate a point (P1) in 3D a certain amount, call it stepSize, along a vector described by a heading composed of ...
1
vote
1answer
86 views

Speedier alternative to “skimage.morphology._pnpoly import points_inside_poly”?

I am using scikit-image's points_inside_poly function, and in my code I am calling it enough times that it takes up about 50% of ...
1
vote
1answer
57 views

Integer simplification of irrational inequality

I'm doing work in computational geometry where the robustness of the algorithm is important. On two separate occasions now have I come across a scenario where I compare the numerical size of two ...
2
votes
1answer
386 views

Unwrap cylinder to plane in Paraview

I want to extract the data from the boundary surface of a cylinder (in a .vtu file) and plot it onto a plane, where the coordinates are theta (rotation angle) and ...
1
vote
0answers
57 views

Algorithm for merging mesh with cad file

I am writing the pre processing program for a porosity based cfd project we just started. Basically I have a 3 dimensional mesh made of cubes and I need to import a STL file over it, and calculate how ...
0
votes
1answer
71 views

difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial ...
5
votes
1answer
79 views

How do you mesh and re-mesh a surface (2-manifold) in 4D?

For ease of explanation, suppose that you began with a two-dimensional surface in (x1, x2, x3, x4)-space, and the surface begins as a flat planar region in the (x1, x2)-plane. The boundaries of this ...
3
votes
3answers
202 views

Surface integration over a portion of an ellipsoid

I would like to perform a surface integration over a portion $D$ of an ellipsoid. A plane arbitrarily intersects the ellipsoid forming two sections, of which one is $D$. I do not know how I can ...
1
vote
0answers
74 views

NURBS surface fitting for a closed region on mesh

I'm developing a tool that allows users to select a closed boundary (a polygon) on the triangle mesh and then from this boundary, generate a NURBS surface fitting the original mesh surface. My idea ...
1
vote
1answer
99 views

Number of faces in a 3D multi-type unstructured grid

Given a 3D unstructured grid consisting of mixed types of shapes (hex, tet, ...), is there a method to know how many faces (including boundary faces) are contained in the grid?
2
votes
1answer
81 views

Mesh with constraints

Is it possible to construct a constrained tetrahedral mesh of a domain using Tetgen or similar software? What I mean by constrained is that there are some nodes or edges that are not free but are ...
2
votes
1answer
383 views

area of voronoi cell

I have a Voronoi diagram that I need to calculate the area of each cell. This Voronoi diagram is produced by Voronoi command in MATLAB. To find the vertices of the Voronoi cell I use ...
4
votes
2answers
61 views

Fitting a surface to scalar functions given on the edges of a triangulation

Given a triangle mesh $\mathcal{T}$ with vertices $V=\{\mathbf{v}_i\}_{i=1}^n$ in $\mathbb{R}^3$ and triangles $T_{ijk}=[\mathbf{v}_i, \mathbf{v}_j, \mathbf{v}_k]$. For each vertex $\mathbf{v}_i$, I ...
2
votes
0answers
78 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is ...
4
votes
2answers
150 views

K-nearest neighbours search in subspaces of a high-dimensional space

I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional ...
2
votes
1answer
84 views

Algorithm to equalize the area of random tessellation of various polygons

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
4
votes
3answers
107 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
54 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...