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
1answer
11 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
46 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
19 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 ...
5
votes
2answers
36 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
5 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
67 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
49 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
11 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
27 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
14 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
28 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
38 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
80 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
42 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
55 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
36 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
46 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
18 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
39 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
82 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
25 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
36 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
78 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
82 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
34 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
27 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
24 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
34 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
167 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
41 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
24 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
21 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
29 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
42 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
60 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
71 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 ...
1
vote
0answers
25 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
0
votes
1answer
23 views

Equality of polyhedra

Is a minimal representation for a polyhedron unique? And if so can we use this to prove that two polyhedra are equal (or maybe the same is a better definition).
0
votes
0answers
18 views

point-tuple orientation

Does something like point-tuple orientation exist? I read this book, pg 336, paragraph "One can even..." and I've bumped into this quite unfamiliar notation. Thanks for clarification. P.S. if someone ...
2
votes
1answer
108 views

points in general position

I'm really confused by definition of general position at wikipedia. I understand that the set of points/vectors in R^d is in general position iff every (d+1) points are not in any possible hyperplane ...
0
votes
2answers
194 views

Hexagonal Tessellation on a sphere

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most ...
1
vote
0answers
44 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...
0
votes
3answers
250 views

determine unit outward normal vector on a curve

It is necessary for me to find unit outward normal vector for the curve: $$\gamma=(x(t),y(t))$$ where $$x(t)=(0.6)\cos(t)-(0.3)\cos(3t)$$ and $$y(t)=(0.7)\sin(t)+(0.07)\sin(7t)+(0.1)\sin(3t)$$ I ...
0
votes
0answers
60 views

quadratic constraints representations

I have two surfaces of parameter $x \in \mathcal{X} \subset \mathbb{R}^n$ with $\mathcal{X}$ to be a polytope: $u(x) = ax + b \subset \mathbb{R}^m, z(x) = x^TAx + B^Tx + C \in \mathbb{R}$. If $m=1$, ...
0
votes
1answer
50 views

Convex hull of a set of points

Let $a_1,a_2...a_r \in R^n$ be points in $R^n$. Prove:$$CH(\{a_1,...,a_r\})=\left\{\sum_{i=1}^r\alpha_ia_i|\sum_{i=1}^r\alpha_i=1,\alpha_i\ge0\right\}=:K$$i.e. the convex hull of the $a_i$ is the set ...