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.

1,229 questions
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 ...
• 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 ...
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 ...
• 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 ...
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 ...
• 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 ...
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 ...
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 ...
• 111
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$ ...
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, ...
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 ...
• 117
1 vote
0 answers
59 views

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 ...
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 &...
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 ...
• 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 ...
0 votes
0 answers
34 views

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 ...
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 ...
• 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,...
• 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-...
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, ...
• 3,280