Questions tagged [computational-geometry]
Using computers to solve geometric problems. Questions with this tag should typically have at least one other tag indicating what sort of geometry is involved, such as ag.algebraic-geometry or mg.metric-geometry.
488
questions
3
votes
0
answers
170
views
Cutting convex polygons into triangles of same diameter
This question continues from: Cutting convex regions into equal diameter and equal least width pieces
Definitions: The diameter of a convex region is the greatest distance between any pair of points ...
- 5,493
1
vote
1
answer
497
views
Line segment-triangle intersection algorithm [closed]
currently in my project I'm using signed tetrahedron volume to check whether a line segment intersects a triangle. Initially I've found this approach in the great answer provided by professor O'Rourke:...
- 169
8
votes
1
answer
314
views
What is the form of the $(v_0,v_1)$-pizza curve?
Assume that there are two (competing) pizza houses situated at the points $0$ and $1$ on the complex plane. These pizza houses can deliver pizza to points of the plane with the largest velocities $v_0$...
- 11.4k
1
vote
1
answer
141
views
On convex polygons contained in convex polygons
In what follows '$n$-gon' stands for '$n$-vertex polygonal region'.
Question: Given a convex $n$-gon $C$, find the smallest convex region $R$ such that $C$ is the smallest $n$-gon that contains it.
...
- 5,493
8
votes
2
answers
334
views
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
- 2,758
15
votes
1
answer
604
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 11.9k
65
votes
3
answers
4k
views
Reasons to prefer one large prime over another to approximate characteristic zero
Background:
In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...
- 3,592
1
vote
0
answers
48
views
Deployment and dispersion in triangular regions
Definitions (from C. Stanley Ogilvy's 'Tomorrow's Math'):
Deployment: To place a specified number $n$ of points (stations) in a region such that the maximum distance of any point in the region from ...
- 5,493
5
votes
1
answer
432
views
Check if a polygon has an axis of symmetry in $O(n)$ time
Question: Is it possible to check if an $n$-gon has an axis of symmetry in $O(n)$ time?
Note: An $O(n^2)$ algorithm is easy to see: it is easy to check if any given line is an axis of symmetry of the $...
- 149k
0
votes
1
answer
1k
views
Fast way to generate random points in 2D according to a density function
I'm looking for a fast way to generate random points in 2D according to a given 2D density function.
For instance something like this:
Right now I'm using a modified version of "Poisson disc&...
CommunityBot
- 1
4
votes
1
answer
202
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
CommunityBot
- 1
1
vote
1
answer
147
views
Total area of cuboids projected on plane
Lets define n arbitrarily scaled, rotated, located cuboids, and plane by normalized direction vector.
Cuboids is supposed to be "flattened" by orthogonal projection on the plane, so we can ...
- 27.4k
3
votes
1
answer
352
views
Computing intersections of unit disks
Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on ...
- 149k
2
votes
0
answers
163
views
Random sets of points and hyperplanes in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.
Consider the random ...
- 149k
1
vote
1
answer
901
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 5,926
6
votes
0
answers
157
views
On cutting disks from planar regions
Question: Given a planar region $R$ of unit area and an integer $n$, to cut $n$ circular disks (their sizes need not be equal) such that the highest fraction of $R$ is taken off.
A simple greedy ...
- 5,493
7
votes
3
answers
2k
views
Algorithm to compute the Voronoi diagram of points, line segments and triangles in $\mathbb{R}^3$
Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?
I know that ...
8
votes
1
answer
762
views
Final project ideas - computational geometry
Next semester I am teaching (the programming part) of a course in Computational Geometry. There are 14 weeks of class, two "pure theory/blackboard" hours per week, one "theory/...
- 149k
0
votes
0
answers
54
views
Attached convex "hulls"
Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
- 12.7k
5
votes
1
answer
351
views
Calculating $n$-dimensional hypervolumes ($n \sim 50$), for example
I have a question regarding efficient and possibly simple algorithms for computing volumes of $n$-dimensional polytopes.
The polytope of concern isn't arbitrary: it is obtained by applying a linear ...
- 141
1
vote
0
answers
177
views
Using Bertini software to determine whether or not a variety is empty
I have a system of polynomials $f_1,\dots, f_n \in \mathbb{C}[x_1,\dots, x_m]$, and I would like to determine whether the set of solutions to the system $f_1(x)=\dots=f_n(x)=0$ is empty or not. Since ...
- 60.2k
6
votes
1
answer
415
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677
1
vote
0
answers
226
views
How to estimate the probability of an edge appearing in the minimum spanning tree of a graph?
I've been running into this problem recently and I've been stuck on it for a while.
I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ vertices (which would also ...
- 5,169
1
vote
1
answer
137
views
Packing L's in Tans and L's in L's
I'm a young researcher and I'm pretty new in this field. I want to work on packing problem "L's in Tans" and "L's in L's" as presented on https://erich-friedman.github.io/packing ....
- 1,924
2
votes
0
answers
23
views
What is known about $\operatorname{card}_E(\mathrm{MST}\cap\mathrm{MWT})$?
It is a wellknown fact of computational geometry that the edges of Minimum-weight Spanning Tree are also found in the Delaunay Triangulation of a planar pointset $\mathcal{P}$, i.e. $\operatorname{...
- 12.7k
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
- 60.2k
3
votes
1
answer
176
views
On some centers of convex regions based on partitions
These questions are inspired by Yaglom and Boltyanskii's 'Convex figures'.
Winternitz Theorem: If a 2D convex figure is divided into 2 parts by a line $l$ that passes through its center of gravity, ...
- 5,493
4
votes
1
answer
199
views
$\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$
I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...
CommunityBot
- 1
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 12.7k
11
votes
0
answers
226
views
When is cohomology of a finitely presented dg-algebra computable?
Given a smooth affine variety $X$ defined over $\mathbb{Q}$, its singular cohomology is isomorphic to the algebraic de Rham cohomology, which is the cohomology of the complex $\Omega_X^0\to\Omega_X^1\...
- 60.2k
5
votes
2
answers
190
views
Fast algorithms for calculating the distance between measures on finite ultrametric spaces
Let $X$ be a finite ultrametric space and $P(X)$ be the space of probability measures on $X$ endowed with the Wasserstein-Kantorovich-Rubinstein metric (briefly WKR-metric) defined by the formula
$$\...
- 1,976
1
vote
2
answers
406
views
Which data structure should I use for hierarchical T-meshes and PHT-splines?
Recently, I'm working on something about polynomial splines over hierarchical T-meshes, which is basically a rectangular grid that allows T-junctions. I want to do some numerical experiments but I don'...
- 4,709
16
votes
3
answers
579
views
How to plot this fractal
I'm a graphic designer and my client has asked me to use this fractal in a design that I'm working on. As you can see, it's not a very good copy, so I'm trying to see if I can generate a high-...
- 263
8
votes
1
answer
218
views
Counting polygons in arrangements
For an arrangement of lines $\cal{A}$ in the plane, an
inducing polygon $P$ is a simple polygon satisfying:
(a) every edge $e$ of $P$ lies on some line $\ell$ of $\cal{A}$, and
(b) every line $\ell \...
- 12.7k
0
votes
0
answers
42
views
Construct pairs of $n$-dimensional convex bodies with given ratios ($p$) of volumes
Given a dimension $n$ and a number $p \in (0,1)$, to what extent is it possible (in what cases) to construct a convex set $A$--not a hypersphere--and a "snugly" inscribed (InscribedFigure) ...
- 723
26
votes
2
answers
4k
views
Why did Robertson and Seymour call their breakthrough result a "red herring"?
One of the major results in graph theory is the graph structure theorem from Robertson and Seymour
https://en.wikipedia.org/wiki/Graph_structure_theorem. It gives a deep and fundamental connection ...
- 121
5
votes
1
answer
153
views
On folding a polygonal sheet
Consider a polygonal sheet $P$ of area $A$ with $N$ vertices (it material is not stretchable or tearable). Let $n$ be a positive integer >=2.
Question: Let $P$ lie on a flat plane. We need to fold ...
- 5,493
2
votes
0
answers
113
views
Computing whether a set of polynomials cuts out a projective variety
I have a set of multivariate polynomials over $\mathbb{Q}$, and I want to compute whether they cut out a projective variety, i.e. whether the radical of the ideal $I$ that they generate is homogeneous....
- 1,010
12
votes
1
answer
375
views
Characteristic polynomial of an $8 \times 8$ symmetric matrix with indeterminate entries related to octonionic multiplication
I consider $1,i,j,k,l,m,n,o$ the standard basis of the (complexified if you like) octonions ($\mathbb{O}$ for the octonions).
Let $a = x_1.1 +\ldots + x_8.o$, $b = x_9.1+ \ldots + x_{16}.o$ and $c = ...
- 106k
7
votes
1
answer
222
views
Computing homology of subvarieties of Euclidean spaces by persistent homology
Let $M$ be a submanifold of the Euclidean space $\mathbb{R}^n$. Let $G$ be a finite group acting on $M$ freely. I want to compute the homology (or even the cohomology ring) of $M/G$.
Suppose the ...
CommunityBot
- 1
2
votes
1
answer
164
views
Existence of solutions of polynomials systems (and their "rough" shape) over $\mathbb{R}$ & friends with positive-dimensional ideals
This is a follow-up (but self-contained) question to my previous one. There I asked about state-of-the-art methods to solve multivariate polynomials systems over non-algebraically closed fields in ...
- 5,169
5
votes
2
answers
336
views
Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?
I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is ...
- 60.2k
4
votes
2
answers
2k
views
How can I efficiently determine which side of a line segment is internal to the polygon?
As part of a larger analysis I have a need to break a polygon into it's individual line segments and mark which side is "inside" of the polygon. If your curious this is going to be fed into a big ...
- 4,618
3
votes
1
answer
381
views
Implementation of Koebe–Andreev–Thurston circle packing?
The circle packing theorem (Koebe–Andreev–Thurston theorem) claims for a planar graph, we can pack disjoint circles, such that: the circles correspond to vertices and the disks are tangent if the ...
- 60.2k
2
votes
1
answer
196
views
Discrete curve-shortening flow – numerical implementation
I need to investigate the properties of open curves which evolve according to the standard curve-shortening flow (Wikipedia link), but with fixed extremes as boundaries (si it should converge to the ...
- 31
3
votes
1
answer
141
views
Natural neighbor interpolation
Recently I am interested in Natural neighbor interpolation, that is :
Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function $$P^*(x)=\sum_{...
- 131
0
votes
0
answers
35
views
Restrictions on crossing edges in Delaunay triangulations
what can be said about crossing edges in Delaunay triangulations, i.e. about pairs of edges that constitute to the heaviest perfect matching int the $K_4$ induced by the quadruplet of adjacent ...
- 12.7k
2
votes
1
answer
351
views
Techniques for refining or constraining a Voronoi diagram?
I have a dataset coming from weather stations where each vertex used to generate the Voronoi diagram is the lat/long of the station. As such, each cell represents the area whose weather is being ...
- 131
3
votes
3
answers
2k
views
Is there a simple criterion to determine if two parallelograms intersect?
Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.
- 1
1
vote
0
answers
34
views
How do I find the portion of a cell/voxel lying within a defined surface?
We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$.
A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
- 111