Skip to main content

Questions tagged [computational-geometry]

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 and surfaces.

Filter by
Sorted by
Tagged with
0 votes
1 answer
46 views

Help troubleshooting ellipse perimeter calculation algorithm

I'm trying to troubleshoot my implementation of an Infinite Series algorithm to calculate the perimeter of an ellipse. I'm sorry I don't have the expertise to express it in, what appears to be a ...
bielawski's user avatar
  • 209
3 votes
1 answer
35 views

Calculate cone direction and angle known quadric function

Now I have the quadric function of a cone: $$\mathbf{x^T} A \mathbf{x} + \mathbf{b^T} \mathbf{x} + c = 0$$ The function is: $$U^T \left( \frac{X - V}{|X - V|} \right) = \cos(\theta)$$ both sides ...
Helloexcel's user avatar
9 votes
2 answers
263 views

Relationship between major and minor axis of an ellipse's circumference

I'm not a mathematician. I'm just doing 3D modeling and can't find an equation to solve this problem. In openscad, an ellipse is created by scaling a circle. So this code creates an ellipse with a ...
bielawski's user avatar
  • 209
0 votes
0 answers
30 views

Incremental algorithm for 2D Linear Programming question for feasible points

I have the following problem that I want to solve using linear programming: $\max\{-3x+12y\}$ (objective function) and 4 contraints: $-x+2y\leq-1$, $2x-3y \leq 6$, $x-3y \leq 0$, $x+y\leq12$ I start ...
average_discrete_math_enjoyer's user avatar
4 votes
1 answer
76 views

A version of Helly's theorem without convexity but connectivity

It's more than 100 years since Helly's celebrated theorem in discrete geometry was published by him, and yet ghosts still remain. The theorem in it's infinitary glory states Let $\{X_j\}_{j\in J}$ be ...
HackR's user avatar
  • 1,802
19 votes
0 answers
1k views

Placing triangles around a central triangle: Optimal Strategy?

Now cross-posted to MathOverflow (link). Question: There is an equilateral triangle. Two players alternate turns placing non-overlapping equilateral triangles of the same size that touch the original ...
Benjamin Dickman's user avatar
0 votes
0 answers
25 views

Closest edge to a rectangle in a plane of rectangles

I have a 2D plane (with discrete points) that contains arbitrary-sized rectangles and all rectangles are axis aligned. I have their coordinates (upper-left) and sizes (length and breadth). Suppose I ...
Harsh's user avatar
  • 1
1 vote
1 answer
29 views

Algorithm to find if intersection of convex sets is empty [closed]

Is there an algorithm to find if the intersection of two convex sets is empty or not. The projection onto convex method (POCS) and similar methods finds a point in the intersection, but will they ...
user221985's user avatar
1 vote
1 answer
63 views

Algorithms to Find Convex Combination Coefficients for a Point within a Convex Polytope Without Explicit Representation

Set Up: Let $P$ be a finite convex polytope. Assume that we do not have a representation for $P$ (like a V-, H- or Z-representation of $P$), all we have is an algorithm which can find a point of $P$ ...
Josstopher's user avatar
1 vote
1 answer
59 views

what is the maximum number of vertices after a 3D planar and regular polygon was truncated by a 3D box?

Let me use a 3D square as an example first. A 3D planar square has four vertices. If this square was truncated by a 3D box, then I can tell that the maximum number of vertices ($NV_{max}$) is eight, ...
Tingchang Yin's user avatar
0 votes
0 answers
18 views

How to morph enclosed mesh according to the enclosing mesh?

I am quite new to meshing and mesh manipulation. I am working on a problem consiting of meshes $A$, $B$, and $C$. The mesh $C$ completely encloses the meshes $A$ and $B$ as shown in the attached ...
Prakhar's user avatar
  • 117
1 vote
0 answers
59 views

Minimal Simplicial Complex from a Sequence of Betti Numbers

I found the following problem in a Computational Topology course that I am following: Write an algorithm that given a sequence $(\beta_0,\ldots,\beta_d)$ of integers builds a simplicial complex whose $...
Pepe's user avatar
  • 126
2 votes
0 answers
36 views

Calculating an ellipsoid with the same distance sum from each point on it's surface to the two foci

I'm a software engineer and look for the answer to a question which I havent found a solution for. So please excuse my bad mathematical terminology in this question. I want to generate an ellipsoid ...
user avatar
0 votes
0 answers
10 views

Stress Vector Tracing algorithm: paper clues and thoughts

I'm looking for someone to aid me in understanding the undefined vectors of this paper I'm hoping that the answer will seem intuitive to someone with a strong understanding of computational geometry. ...
Lyndon Alcock's user avatar
0 votes
0 answers
27 views

Reading The Null Space/Kernel Of A Matrix (In RREF) Algorithmically

My goal is to compute the normal vectors of hyperplane, for which an explanation can be found in the answers of this post. For this I have written Gaussian elimination algorithms to convert the matrix ...
Ood's user avatar
  • 121
0 votes
1 answer
25 views

Compute the exterior dihedral angle between two hyperplanes

Let's say, in $d$-dimensional space, we have two hyperplanes: $\mathbf{n_1}\cdot\mathbf{x}+b_1=0$ and $\mathbf{n_2}\cdot\mathbf{x}+b_2=0$ respectively, and their normal directions satisfy $\Vert\...
Karbo Lei's user avatar
1 vote
1 answer
86 views

Covering a Polygon with circles with a constant radius of $r$

"I am currently engaged in optimizing the placement of sensors in an agricultural field, inspired by the problem outlined in the paper 'Approximation Algorithms for Robot Tours in Random Fields ...
iman moghadari's user avatar
1 vote
0 answers
59 views

The only irreducible triangulation of $S^2$

I have been reading "An Introduction to Computational Topology" by Herbert Edelsbrunner and John Harer and they give the following exercise question in the second chapter of the book on &...
srnl10695's user avatar
0 votes
1 answer
62 views

Is There a Conceptual Connection Between the 3D Winding Number and Ray Casting Algorithms?

The 3D winding number provides a numerical answer to whether a point is inside or outside a closed surface, with its definition arising from surface integration. In my recent journey through ...
K.R.Park's user avatar
  • 113
2 votes
0 answers
36 views

Calculation of the Picard group and the class group [closed]

I am thinking about the computation of the class group and the Picard group for the case of Number fields over $\mathbb{Q}$ and $\mathbb{F}_p(t)$ Complex varieties I would like to know what kinds of ...
user avatar
0 votes
0 answers
34 views

Computing $\epsilon$-packing sets in Euclidean space

Let $\epsilon > 0$. For $P\subset \mathbb R^d$, a subset $Q\subset P$ is called an $\epsilon$-packing if: for every $p \in P$ there is a $q\in Q$ such that $d(p,q) \leq \epsilon$, and for every $q,...
pyridoxal_trigeminus's user avatar
0 votes
0 answers
12 views

Accessibility from start position to goal position in 2d plane

Given a vehicle with irregular shape in 2d plane, and its start position and start orientation, like (sx, sy, sori), and also its goal position and goal orientation, like (gx, gy, gori). Between the ...
Lym Zoy's user avatar
  • 101
3 votes
1 answer
111 views

Decomposing a vector to two vectors

There is a statement by professor in class that every vector $\vec p$ could be decomposed to whatever other two vectors $\vec u$ and $\vec v$ for which ${\vec u \times \vec v \neq 0}$. So they are not ...
vikAy's user avatar
  • 141
0 votes
2 answers
67 views

Geometry tricks for smallest of 2 circles circumscribing points

I’m trying to find which of two circles A,B,C and A,B,D has a smaller radius, where A,B,C,D ...
Andrew's user avatar
  • 3
4 votes
3 answers
179 views

Prove that every simple polygon has a ear without resorting to triangulation

We can establish the existence of a triangulation for each simple polygon relying on the fact that every simple polygon has at least one ear, utilizing induction. Conversely, we can establish that ...
log2's user avatar
  • 475
1 vote
0 answers
36 views

Rounding error accumulation and workaround. Collision detection.

I do not know, fellows, how best to describe my problem. But I will try my best. I think this question is more for mathematicians than programmers. There is 2 objects (fig.1): One object is a wall (...
Alex NJ's user avatar
  • 109
0 votes
0 answers
36 views

Aligning a Lower-Dimensional Object With A Plane

Given an n-1 dimensional simplex in n-dimensional space (at an unknown rotation), I am looking for a way align the object with a given plane, i.e. rotate it in such a way that the coordinates for that ...
Ood's user avatar
  • 121
2 votes
0 answers
101 views

Triangulation Around a Point in Any Dimension

Given a set of randomly distributed points in n-dimensional space, I am looking for a way to algorithmically find the optimal simplex (no sharp angles if there are multiple options) surrounding a ...
Ood's user avatar
  • 121
0 votes
0 answers
41 views

Algorithm to recognize spherical abstract polytopes

A finite abstract polytope of rank 3 (an abstract polyhedron) consists of adjacency data for a collection of polygonal faces and their shared edges and vertices. This data is sufficient to uniquely ...
Karl's user avatar
  • 11.8k
1 vote
1 answer
72 views

What shape is formed by the bounded coefficients of a quadratic polynomial with only real solutions when the coefficients act like 3D tuples?

Back Story I believe a quadratic polynomial, $ax^2+bx+c$, has only real solutions $\text{iff}$ the discriminant, $D \geq 0$, which occurs when: $$ D = b^2 - 4ac \geq 0 \Rightarrow \begin{cases} b^2 ...
Teg Louis's user avatar
1 vote
0 answers
79 views

What kind of algorithm would solve this problem: shortest routing between 3D cubes

I have these in 3D space: Green points where blue routes begin 🟢 Black hole/sphere where all blue routes end ⚫ Red cubes that must not have any collision with blue routes 🔴 Blue routes beginning ...
Megidd's user avatar
  • 271
0 votes
0 answers
15 views

Surface Discretization with Equi-Sized Squares

I am currently working with a triangulated surface, represented by a list of vertices (x, y, z coordinates) and triangles defined by three vertices each. Notably, the triangles vary in size, and their ...
roymustang's user avatar
0 votes
0 answers
34 views

Convexification of facility location problem

I have a set of service locations $\{ {\bf{x}}_i \in \mathbb{R}^2\}_{i = 1}^{N}$. I have $k$ facilities to locate in a way that distance of each service point to the nearest facility is minimized. My ...
Eric Johnson's user avatar
1 vote
1 answer
64 views

is every triangulation of regular n-gon has same minimum angle?

Although my knowledge maybe not correct, but I will state it nonetheless; "Delaunay triangulation maximizes the minimum angle among all triangulation" "Every triangulation of regular n-...
K.R.Park's user avatar
  • 113
1 vote
1 answer
74 views

How to efficiently calculate which region a polygon is in relation to a polynomial with a pencil-and-paper procedure?

A polynomial splits $\mathbb{R}^2$ into 3 regions: above, below, and where the polynomial lies. A polygon is made up of line segments. The polygon's spatial relationship to a polynomial can be one of ...
Teg Louis's user avatar
0 votes
0 answers
47 views

Size of an $\epsilon$-net on n-qubit unitaries

I am currently reading through Computational Quantum Entanglement paper and there is a following statement there in proof of Lemma 4.1 We then use that an $\eta$-net (this is an $\epsilon$-net with ...
Piotr Lewandowski's user avatar
2 votes
0 answers
86 views

Defining a convex "hole"

How could we define the idea of the inverse of the convex hull? To clarify, not what is the innermost convex hull without recursively drawing and removing convex hulls, but maximizing a convex shape ...
IainMcE's user avatar
  • 21
0 votes
1 answer
70 views

Minimum volume sphere bounding all points as a linear programming problem

I want to find the smallest sphere which encapsulate a set of points $x_i \in \mathbb{R}^d$. I can formulate is as $$ \arg \min_{a \in \mathbb{R}^d, r} r \quad\quad \text{s.t.} \quad || x_i - a|| \leq ...
Mark's user avatar
  • 121
1 vote
0 answers
64 views

If p is a vertex on the convex hull of S, then the farthest-point voronoi region of p is not empty [closed]

I am given a set $S$ of points and I want to prove that for any point $p$ in $S$, the farthest-point voronoi region of $p$ is not empty if and only if $p$ is on the convex hull of $S$. I denote ...
ali nakhaee's user avatar
1 vote
0 answers
87 views

Get 3d ray in world coordinates from a 2d pixel location

I am trying to project a 3d ray from a 2d image pixel location. I have the actual 3d coordinates of a pixel location and want the ray from the camera to intersect this point but currently, my line is ...
Mattcc18's user avatar
4 votes
0 answers
172 views

How to find the "sum" of two parametric curves?

Given two parametric 2D curves: $c_1=[x_1(a),y_1(a)], \text{ for } a\in[0,1]$ $c_2=[x_2(b),y_2(b)], \text{ for } b\in[0,1]$ I want to find the "sum" of these curves, which I define as the ...
Franco's user avatar
  • 41
0 votes
0 answers
59 views

Ordered Delaunay triangulations

I would like to show that, given n points in the plane $q_1 ... q_n$ such that the distance between $q_0$ and $q_i$ is smaller than or equal to the distance between $q_0$ and $q_j$ for every $i < j$...
Baksel's user avatar
  • 81
2 votes
1 answer
49 views

Finding a bounding box for convex polytope, specified by linear inequalities

given a set of linear inequalities (and equalities) I want to find a bounding fox for it. There is an obvious straightforward solution, but I hope it is possible to convert the whole problem to one ...
stiv's user avatar
  • 147
1 vote
0 answers
42 views

Why this $2$-dimensional polytope has two different half-space representations? What is the geometrical intuition behind this?

Let a $2$-dimensional polytope given by the vertices $P_1=(0, -1)$, $P_2=(-1, 0)$, $P_3=(-1, 2)$, $P_4=(1, 0)$, $P_5=(1, -1)$: When I use different libraries to obtain the half-space representation, ...
Eldar Sultanow's user avatar
1 vote
0 answers
34 views

Computing a closed cone

Suppose we have a vector valued smooth function $F(x) = [f_1(x),f_2(x),f_3(x),...,f_n(x)]^t$ defined for $x \in \mathbb{R}^n$. Suppose we are given a rectangular domain $M = [a_1,b_1] \times [a_2,b_2] ...
Llamawithakeyboard's user avatar
3 votes
1 answer
108 views

Can we predict if two line segments on the plane will intersect each other?

Let $X$ be a non-empty set of 4 points in the plane, and $(X,\mathrm{d})$ the euclidean metric on $X$. Let $(x_0,y_0)\in X^2$ be any pair of points in $X$ and $\overline{x_0y_0}$ a straight line ...
Simón Flavio Ibañez's user avatar
0 votes
2 answers
89 views

Picking the point on a sphere furthest from all points?

2D Version of the problem (With tentative solution) You are given a set of vectors $V = \{v_i\}$ And you are guaranteed that they are all unit length. You want to find a vector $x$ such that $x$ is as ...
Makogan's user avatar
  • 3,439
2 votes
0 answers
27 views

algorithm for the volume of the intersection of $m$ balls in $\mathbb{R}^n$

Is there an algorithm for computing the volume of the intersection of $m$ balls in $\mathbb{R}^n$ for $m,n \in \mathbb{N}$? That is, we want to compute the volume of $$ \bigcap_{k=1}^m \mathcal{B}(C_k,...
C Marius's user avatar
  • 1,291
1 vote
1 answer
39 views

voronoi diagram has at most quadratic complexity

I am reading the book "computational geometry" by Mark the Berg, Cheong, van Kreveld, Overmars (link to the book: https://erickimphotography.com/blog/wp-content/uploads/2018/09/Computational-...
andrealorenzetti's user avatar
2 votes
2 answers
193 views

Triangulating a polygon

First please let me introduce some terminology in order to avoid misunderstandings (forgive me if it is a bit tedious). Consider a collection of finite number of planar, consecutive line segments, ...
dmtri's user avatar
  • 3,280

1
2 3 4 5
25