All Questions
Tagged with computational-geometry reference-request
38
questions
8
votes
0
answers
175
views
Placing triangles around a central triangle: Optimal Strategy?
This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
- 7,771
1
vote
0
answers
114
views
Explicit computation of Čech-cohomology of coherent sheaves on $\mathbb{P}^n_A$
$\newcommand{\proj}[1]{\operatorname{proj}(#1)}
\newcommand{\PSP}{\mathbb{P}}$These days I noticed the following result of (constructive) commutative algebra, which I think is probably well known ...
- 650
1
vote
0
answers
80
views
Counting Voronoi cells generated by lattice points
I am working on a problem in dynamical systems where I need to count Voronoi cells arising from nearest neighbours to a subset of the lattice. (See the picture below for an example: the shaded region ...
- 22.7k
3
votes
1
answer
103
views
Results in computational geometry utilizing doubling dimension of a metric space
According to Wikipedia,
However, many results from classical harmonic analysis and computational geometry extend to the setting of metric spaces with doubling measures.
My question is: what are some ...
2
votes
0
answers
53
views
Cylinder orientation representation
I'm trying to find an efficient computation and representation for the following problem.
Given a cylinder with height $h$ and radius $r$ with a given position $\mathbf{x} = [x, y, z]$ and $N$ number ...
- 21
5
votes
2
answers
194
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
$$\...
- 41.1k
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 ...
- 280
4
votes
1
answer
421
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 ...
- 1,445
4
votes
1
answer
203
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 ...
- 469
5
votes
0
answers
350
views
Are nearby points in an algebraic curve necessarily connected?
I would like a result of the following form:
For every algebraic curve $C$ in $\mathbb{R}\mathbf{P}^{n-1}$, there exists an
explicit and easy-to-compute $\epsilon=\epsilon(C)>0$ such that ...
- 7,593
4
votes
2
answers
385
views
Complexity of Random Delaunay Triangulation in 3D
My question:
Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one?
which is equivalent to the question
Is the ...
- 141
4
votes
2
answers
424
views
largest diameter of intersection of two balls
Two closed balls with a common radius are positioned so that the centre of either ball is on the boundary of the other.
I am interested in the extremal diameter of their intersection, in an arbitrary ...
- 2,330
4
votes
2
answers
330
views
How many dihedral angles need to be specified to uniquely specify a triangulated polyhedron?
Suppose you are given a simplicial complex $K$ homeomorphic to the sphere and for each each edge of the complex a label specifying a length of that edge (this gives us a polyhedral metric on $K$). In ...
- 185
2
votes
0
answers
111
views
How to compute explicit equations for the Jacobian of a variety over a field [duplicate]
Suppose we start with a projective curve $X$ over a field $K$, given as a closed subvariety of $\mathbb P^n_K$ by some explicit list of equations. I would like to find an explicit representation of ...
- 374
1
vote
0
answers
97
views
Geometry of a $(d-1)$-dimensional lattice
Let $\mathbf u\in\mathbb Z^d$ be a primitive vector (i.e. $\gcd(u_i)=1$) and let $\Pi_{\mathbf u^\perp}$ be the orthogonal projection perpendicular to $\mathbf u$. I want to understand the geometry of ...
- 22.7k