The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves ...

learn more… | top users | synonyms

0
votes
0answers
25 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
2
votes
0answers
49 views

3D kinematic geometry problem motivated by chemistry

It is well known that six carbon atoms can form a ring called cyclohexane. Since the angle between bonds is $\cos^{-1}\left(\frac{-1}{3}\right)\approx 109^\circ$, the ring is not a planar hexagon. ...
0
votes
1answer
31 views

Tetrahedron subdivision

What are all the possible subdivisions of the P3 tetrahedron (i.e. for each face, 3 vertices plus two points per edge, located at 1/3 and 2/3, and the centroïd of the face, so a total of 20 points for ...
1
vote
1answer
20 views

How to find the closest line to two segments?

I have two segments in 2D space, defined by their endpoint x and y coordinates. How can I find a best-fit line using vector algebra (formally, that minimizes the integral of square-distance from it to ...
0
votes
0answers
8 views

Rotational normalisation of a sequence using PCA

I have a 1D contour, defined as a sequence of points in 2D space. For arguments sake, lets say I want to achieve rotational normalisation by aligning the direction of the first principal component of ...
0
votes
0answers
37 views

Unique Cicum-Sphere in n-Dimensions

I want to know if there is a generic way to find the circumcenter of an (n-1)-simplex in n-dimensions. Does there a exist a unique sphere which passes through n-points in n-dimensions? For example say ...
6
votes
2answers
82 views

How to determine whether a point is inside a closed region or not?

Take the following parametric equation of an implicit curve as an example: $$ \left\{\quad \begin{array}{rl} x=& 9 \sin 2 t+5 \sin 3 t \\ y=& 9 \cos 2 t-5 \cos 3 t \\ \end{array} \right. $$ ...
0
votes
0answers
29 views

Relation between parallel transport and Jacobi field II

Before I asked a question here: Relation between parallel vector field along a geodesic and Jacobi field along that same geodesic The current question is related, and actually arise from numerical ...
0
votes
1answer
24 views

finding volume of an n-dimensional pyramid numerically

In my experiment I need to compute hypervolume/area from a set of points, let's start with a base case -- Triangle: In this case, I have 3 points in a 2D space and they make a triangle, $p_1 = ...
0
votes
1answer
16 views

Voronoi diagram of a set of vertices of a mesh.

i have a triangulated mesh. I have some vertices which are part of the vertices of the mesh. Is there any algorithm to compute the voronoi diagram of these set of vertices. The triangulated mesh ...
1
vote
2answers
75 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. Basically what I am looking for is the center of the smallest sphere which passes through all 4 vertices of the ...
2
votes
0answers
28 views

Compute volume of the tetrahedron from circumsphere test

I'm working on a computational geometry algorithm. In every iteration I solve the matrix below, where (a,b,c,d) are the vertices of a tetrahedron, and e is an arbitrary point. Solving the determinant ...
6
votes
3answers
69 views

Way to measure the similarity/difference of 2D point clouds

i need a way to measure the similarity or difference of two point clouds? The number of points in each point cloud can be different. The Point clouds are already aligned. By similarity I mean the ...
0
votes
0answers
6 views

Equalize length of 1-ring edges of vertex

My question is how to equalize the length of edges in 1-ring neighbours of while-circled vertex in the below figure Hope to see your answer!
1
vote
0answers
74 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
1
vote
2answers
53 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
0
votes
0answers
12 views

Prove Theorem with Groebner Basis

I'm trying to prove some theorems using Groebner Basis (as described in Cox, Little and O'Shea Link ) The mentioned book gives as an excercise to prove Pappus theorem using the given methodology, ...
0
votes
1answer
34 views

How do I calculate center of mass of a grid-type object?

I am making a game with 2D objects that are grid based. These objects are made out of tiles that are actually the cells of the grid. Each tile has a "mass" that is more than 0 and no upper limit. I ...
0
votes
1answer
31 views

Find all nearest points

I have two sets: $$P = \{p_1, p_2, ..., p_n\}$$ $$Q = \{q_1, q_2, ..., q_m\}$$ For each $p_i$ point I need to find all nearest points in $Q$. I.e., $$p_i \rightarrow \{ q_{i_1}, q_{i_2}, ..., ...
0
votes
1answer
16 views

Given a known line segment and two known horizontal lines, how do I find the line subsegment between the two parallels?

I am trying to clip a line segment between two parallel horizontal lines. I know the location of the two vertices on the larger segment, but need to know the points at which it intersects the ...
0
votes
0answers
34 views

What is the mathematics behind the two animations?

I found two animated GIFs from a designer's website, which looks very impressive: My questions are: what is the mathematics behind them? How to obtain the mathematical formulas and equations of ...
0
votes
1answer
30 views

What does R^d in last lines refer to

The image above is snapshot in the journal Geometric Approximation http://sarielhp.org/papers/04/survey/survey.pdf via Coresets .I could not figure out what is ...
0
votes
1answer
55 views

Knowing only the coordinates of the North-East and South-West corners of a rectangle, how to check if a point is inside a rectangle?

This is similar to this question. What's different is that only the coordinates of the North-East and South-West (or North-West and South-East) corners are known. My question is, can you directly ...
-2
votes
1answer
83 views

(x,y) coordinates from gluing together a sequence of right triangles with arbitrary angles [duplicate]

I have been scratching my head all day over this question for one of my assignments. I haven't made any progress and I'm at the point of giving up. Here's what I need help with. Start by gluing ...
2
votes
1answer
45 views

Bounding Sphere for Two Hyperrectangles

Please see the image for best illustration of the task. I have two hyperrectangles, $\text{R1}$ and $\text{R2}$, whose exact location and size is arbitrary. Now, my task is to construct a bounding ...
0
votes
0answers
58 views

What is the shape of the set of integer sided acute triangles with largest side n?

I played around with Gauss circle problem and found that if you take a certain sum in reverse and "in forward" and subtract the resulting sequences you get the OEIS sequence: https://oeis.org/A247588 ...
0
votes
0answers
41 views

does any polyhedral partition admit a convex piecewise quadratic surface defined over?

Given a polyhedral partition, i learnt that there exist some conditions for the existence of a convex piecewise affine surface over this partition for example the following study. ...
0
votes
0answers
55 views

How to use CVX to solve this problem?

I have a function in the variables $x_{kl};\ k,l=1\ldots,m$, $$\sum_{i=1}^n \sum_{j=1,j<j'}^{N_i}\left( b_{ij} b_{ij'}- \sum_{k,l=1}^{m}x_{kl}f_k(a_{ij})f_l(a_{ij'})\right)^2$$ where ...
1
vote
0answers
22 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
1
vote
0answers
43 views

Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
1
vote
1answer
89 views

What is a composition of two binary relations geometrically?

the composition was defined as follow: (a,b) \in (R;S) <=> there is c | (a,c) \in R and (c,b) \in S . If our two relations R and S are two convex polygon ...
0
votes
1answer
34 views

How to compute Convex hull of set points from voronoi diagram

Assume $n$ points in the plane and their Voronoi diagram are given, prove that the convex hull of the points can be computed in linear time.
1
vote
1answer
49 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
7
votes
0answers
79 views

Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ Definition: Quadruple of points $(u_{i}, ...
2
votes
2answers
95 views

Find polygon with smallest perimeter that encompasses all points

Given a random set of points in 2D space such as: How would one go about finding the smallest perimeter polygon that encompasses all points and has a point as each one of its vertices? For the ...
1
vote
1answer
36 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
2
votes
0answers
28 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
0
votes
0answers
27 views

What does “maximum geometric error of a chunk” mean?

In this paper, on the top of page 7 it says, Where $\delta$ is the maximum geometric error of a chunk ... What does that mean? Thanks :D
0
votes
0answers
41 views

How to navigate around a smooth surface?

Suppose I want to find the shortest path between two points in $\Bbb{R}^3$ with smooth obstacles in the way? I understand things like Dijkstra's algorithm for shortest paths on a graph. But what about ...
3
votes
1answer
48 views

Graphing algorithm

I am not sure if this belongs on Mathematics Stack Exchange, but it is somewhat relavant here. The Problem If you've installed any graphing/plotting apps on your smartphone, you will notice that the ...
0
votes
0answers
17 views

Ways of partitioning n points into some cubes

Assume there're $n$ fixed points in $\mathbb{R}^d$ contained in a ball with radius $M$,and you can partition the space by cubic grid with cube's edge length $h>\epsilon$. How many different ways of ...
1
vote
0answers
36 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
13
votes
1answer
171 views

Automorphism group of a lattice's Voronoi cell

Let $\Lambda$ denote a lattice of $\mathbb{R}^n$, i.e. $$\Lambda = \left\{\sum_{k=1}^n n_i\mathbf{a}_i\ \bigg|\ n_i\in\mathbb{Z}\right\},$$ for $n$ linearly independent vectors $\{\mathbf{a}_i\}$ in ...
0
votes
1answer
49 views

How to determine if some line segments are collinear

Let's say I have several Line Segments that are connected to each other and make a Polyline. How can I determine if they are ...
0
votes
1answer
25 views

How do I place two points on two axis-aligned line segments such that they have given Euclidean distance l?

This is my problem: I am given two axis aligned line segments $l_1$ and $l_2$ of finite length and a distance $l$. How do I find points $p_1 \in l_1$ and $p_2 \in l_2$, such that $||p_1-p_2||_2 = l$? ...
1
vote
0answers
22 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
0
votes
1answer
32 views

Finding other two vertices of a triangle from centroid and one vertex?

I am working on some gesture recognition for my game and I want to find if a point is inside the triangle created by the user or not. For that I need three vertices. Currently I am using the '$1 ...
0
votes
1answer
47 views

Hypersphere - Pattern matching using Centroid, Radius and Diameter

I have a hyper-sphere formed with set of $n$-dimensional data points. I could calculate centroid ($X_0$), radius($R$) and diameter($D$). Using these $X_0, R, D$, how I can find whether the a given ...
0
votes
1answer
69 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or mathoverflow. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside ...
0
votes
2answers
87 views

Scan line algorithm for intersecting polygons

Given two sets of polygons $P_1 = \{s_1,...,s_m\}$ and $P_2=\{s_m+1,...,s_n\}$ with total number of $n$ segments, the previous and next segment on it's polygon can be determined in $O(1)$. Describe a ...