All Questions
Tagged with computational-geometry algorithms
67
questions
1
vote
0
answers
64
views
Algorithm to generate configurations with kissing number 12
That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...
- 111
4
votes
2
answers
201
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
3
votes
1
answer
244
views
Resultants and elimination theory
Consider an ideal $I = \langle f_1,\dotsc,f_n\rangle$ in the ring $k[x_1,\dotsc,x_m]$.
Define the $i$-th elimination ideal to be $I_i = I \cap k[x_{i+1},\dotsc,x_m]$.
For any two polynomials $f$ and $...
- 1,425
5
votes
1
answer
250
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 19.3k
5
votes
0
answers
165
views
Computing sums with linear conditions quickly
Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
- 19.3k
1
vote
0
answers
36
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
- 11
7
votes
1
answer
347
views
Finding maximal prefix of a simple curve
Let $S$ be a simple curve. I want to determine maximal prefix of $S$ contained in a unit circle. Is this possible, or has it perhaps already been solved in the past, and I am just unable to find an ...
- 71
15
votes
1
answer
355
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 3,369
3
votes
0
answers
49
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,039
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.8k
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.8k
6
votes
1
answer
418
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,667
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&...
- 121
4
votes
2
answers
212
views
Algorithm for reporting all triangles with unique interior point
What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
- 12.8k
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