All Questions
Tagged with computational-geometry algorithms
67 questions
1
vote
0
answers
65
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
219
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
271
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,435
5
votes
1
answer
255
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 $\...
- 20.2k
5
votes
0
answers
167
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 ...
- 20.2k
1
vote
0
answers
38
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
348
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
359
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,399
3
votes
0
answers
51
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,079
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 ...
- 13.2k
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 ...
- 13.2k
6
votes
1
answer
424
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
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
213
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, ...
- 13.2k
4
votes
1
answer
204
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 ...
- 479
5
votes
3
answers
149
views
Fast computation of a ball with radius r with largest number of input points
We are given a set S of n points equipped with some metric and an integer $r>0$. We define $B(x,r) \subseteq S$ (the ball with radius r centered in x) to be the set of points in S within distance r ...
- 51
2
votes
1
answer
213
views
Intersection of sphere with triangle containing moving vertices
First off, apologies if I cannot properly articulate my question in the most formal way. However, I believe my question should be simple enough to grasp anyhow.
In $\mathbb{R}^3$, I would like to ...
- 121
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
2
votes
1
answer
270
views
Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane
I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...
- 51
4
votes
2
answers
145
views
Complexity of Determining the Edges of Planar Convex Hulls
Question:
can the set of edges that resemble the convex hull ($CH$ for short) of $n$ points in the euclidean plane be determined in $O(n)$ time?
I know that the time complexity of determining the $CH$...
- 13.2k
4
votes
2
answers
734
views
Fast projection onto a subspace
Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
- 1,677
1
vote
0
answers
117
views
The upper bound of the number of points of a convex hull formed by external co-tangents of circles
Consider the following problem: Given a rope to surround some circles, and minimize the length of the rope.
In order to solve the problem, we shall calculate all external co-tangents of these circles, ...
- 601
1
vote
0
answers
63
views
Congruency check for set of points in 3D using inertia tensor
You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...
- 1,171
0
votes
1
answer
67
views
Calculating a Measure of the Geometric Complexity of Planar Closed Polylines
Let $\lbrace p_1,\ \dots,\ p_n\rbrace$ be a set of points in the Euclidean plane and let $T_0 :=\left(p_1,\ \dots,\ p_n,p_1\right)$ be a Hamilton cycle through the set of points.
Question:
...
- 13.2k
2
votes
1
answer
91
views
Generating Convex Polygonal Neighborhoods from Triangulations of Discrete Pointsets
The wellknown Delaunay Triangulation $DT$ has as a straight line dual the also wellknown Voronoi Diagram $VD$.
Both are most commonly defined in the Euclidean plane and are primarily beneficial for ...
- 13.2k
5
votes
1
answer
2k
views
Intersections of quadratic planes as elliptic curves
An elliptic curve defined over a field $k$ is a smooth projective curve of genus $1$, plus a $k$-rational point. Every elliptic curve can be written in a Weierstrass form, i.e. as a plane cubic curve ...
- 3,432
4
votes
1
answer
519
views
A brief question about the "Eight Queens" Puzzle
The classical Eight Queens puzzle asks whether it is possible to arrange $ 8 $ queens on an $ 8 \times 8 $ chess board, so that no two queens attack each other.
It is well-known that such ...
- 337
2
votes
0
answers
486
views
Finding good high-dimensional sphere coverings in Euclidean space
Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...
- 733
5
votes
1
answer
169
views
Connectedness of semialgebraic sets via CAD
I do not know whether there is a standard or some traditional ways to decide whether a semialgebraic set is connected or not.
One way I know is the cylindrical algebraic decomposition (CAD) algorithm. ...
- 61
8
votes
3
answers
389
views
A simplified Art Gallery Problem in a matrix
Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
- 549
0
votes
0
answers
63
views
Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere
Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
user76479
2
votes
1
answer
69
views
Maximal opening angle of a polygon from a point [closed]
I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...
- 121
4
votes
2
answers
2k
views
Breaking a rectangle into smaller rectangles with small diagonals
Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
- 4,049
10
votes
1
answer
3k
views
Computionally efficient vertex enumeration for (convex) polytopes
Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
- 321
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 41
1
vote
2
answers
680
views
Regular paths along surface of sphere
I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...
- 133
0
votes
1
answer
116
views
Paper on unit disk graphs
I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?
- 903
3
votes
2
answers
333
views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
3
votes
2
answers
1k
views
Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances
Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
- 41
1
vote
0
answers
58
views
Covering a set of points by bounded geometric object/objects
1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$.
2) Also, in general setting, the problem is to ...
- 285
4
votes
3
answers
2k
views
Hyperrectangle partition of set of overlapping hyperrectangles
I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...
- 151
6
votes
1
answer
5k
views
Finding the vertices of a convex polyhedron from a set of planes
I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...
- 171
7
votes
1
answer
3k
views
Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?
Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...
1
vote
1
answer
226
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
- 851
4
votes
1
answer
821
views
Checking if a binary vector lies in the affine span of given binary vectors
Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...
- 41
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 165
2
votes
0
answers
697
views
Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin
Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...
- 21
6
votes
2
answers
2k
views
Find minimum-area ellipse which encloses two ellipses
I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...
- 61
3
votes
2
answers
1k
views
Enclosing a set of ellipses within one ellipse
Is there an algorithm that takes in a set of ellipses and gives back an ellipse that encloses the original set of ellipses?
- 147
11
votes
3
answers
960
views
Algorithms in Invariant Theory
Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$.
In chapter 4.6 of his book "Algorithms in Invariant ...
- 262