Questions tagged [computational-geometry]
The computational-geometry tag has no usage guidance.
45
questions with no upvoted or accepted answers
18
votes
0answers
407 views
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
10
votes
0answers
141 views
Which convex polytopes have volumes of polynomial bit-length?
A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex ...
5
votes
0answers
84 views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
5
votes
0answers
71 views
Computing 3D viewpoint of a set of non-intersecting segments
Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two ...
5
votes
0answers
54 views
Inapproximability Results for APX-hard Geometric Optimization Problems
A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
5
votes
0answers
108 views
Structures obtained by gluing simplices
I'm looking for the correct name of geometric structures obtained as follows.
2-structures: A collection $X$ of triangles is a $2$-structure. If $X$ is a $2$-structure and $Y$ is obtained from $X$ ...
5
votes
0answers
272 views
Total time complexity of convex hull problem
The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a ...
5
votes
0answers
74 views
Finding of dimension of algebraic varieties
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).
Are ...
4
votes
0answers
49 views
$\ell_\infty$ partially enclosing ball problem
Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? ...
4
votes
0answers
140 views
Computing Minima of the Projection of a Binary Cube
The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
4
votes
0answers
215 views
Voronoi diagram in presence of polygonal obstacle
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.
The distance between a point $p \in ...
3
votes
0answers
71 views
Rearranging angles of a convex polyline to make it closed
Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by ...
3
votes
0answers
108 views
Equivalence of weighted Minkowski sums
Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices.
Furthermore, consider a variant of the Minkowski sum (somehow ...
3
votes
0answers
76 views
Triangular range counting query in poly-logarithmic time
What is the minimal space requirement for
triangular range counting queries in plane
if one wants to process each query in poly-logarithmic time?
In [Goswami et al, 2004]
they preprocess the ...
2
votes
0answers
28 views
Complexity of best folding of a 2D set (or how to optimize a sandwich)
Motivation:
I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
2
votes
0answers
54 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 ...
2
votes
0answers
49 views
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
And if there is, what is the computational ...
2
votes
0answers
49 views
Lower bound on light spanners in Euclidean space reference
It is well-known that Euclidean space of dimension $d$ has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}\cdot w(MST)$ (see Chapter 14 of Geometric Spanner Network book by Narashimhan ...
2
votes
0answers
126 views
Weighted $l_1$ distance
So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
2
votes
0answers
546 views
Shortest non-crossing geometric paths
I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
2
votes
0answers
201 views
Inclusion of polytopes
Consider the following two system of linear (in)eqaulities:
$S = Ax \leq b;\; Cx = e$
$T = Dx \leq d;\; Gx = g$
How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
2
votes
0answers
71 views
Check whether a point is a vertex of Minkowski sum of polytopes
Given $n$ polytopes
$$\begin{align*}
P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\
P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
2
votes
0answers
60 views
How to compute the basis
Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and
$W=
\begin{...
2
votes
0answers
213 views
Convex hull of polytopes
Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a
structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
2
votes
0answers
43 views
centralized deterministic Spanner construction with low degree and low stretch
Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
2
votes
0answers
194 views
Eulerian Triangulations
Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree.
I cam across this page http://cs.anu.edu....
2
votes
0answers
108 views
Worst-case optimal Delaunay algorithm based on spatial sort and walking?
Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a ...
2
votes
0answers
129 views
Tiling a rectangle with weighted cells (min-max problem)
Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by ...
1
vote
0answers
39 views
Practical worst-case polylogarithmic dynamic orthogonal range queries?
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
1
vote
0answers
64 views
Mapping of entire balls using Locality Sensitive Hashing (LSH)
LSH functions are useful for approximate nearest neighbor search.
They are usually defined, for distance metric $d$ and $c>1$ as follows:
A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
1
vote
0answers
83 views
LSH Probabilistic guarantees
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:
$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \...
1
vote
0answers
76 views
Points of a finite set wihtin a ball
I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$.
In particular, I would like to be able to solve the problem of finding all the point ...
1
vote
0answers
110 views
Hausdorff Distance and Convex Hull
Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
1
vote
0answers
92 views
Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs
I'm interested in complexity results for Maximum Independent Set (or Vertex Cover) problem over the class of disk packing graphs. Having a set of disks we build a graph that has its vertices at the ...
1
vote
0answers
75 views
Compute basis of vertex set of polytope
I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.
Formally,
INPUT: a polytope
$$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
1
vote
0answers
29 views
Extending Delaunay graphs in d-space
I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space.
...
0
votes
0answers
31 views
Are generalized map involutions captured by GNN?
In coming across a post related to this question's topic, posting in Theoretical Computer Science might be the right place. In combinatorial maps (1,2,3), are generalized map involutions captured by ...
0
votes
0answers
86 views
How many maximal planar graphs are there?
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
0
votes
0answers
30 views
What is the best way to find circles that contain a given point (in 2D)?
Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions.
...
0
votes
0answers
48 views
Volume computation of special polytopes
I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so.
I know that in general it is #P-hard to compute the volume of $\mathcal{H}$
-...
0
votes
0answers
31 views
Does optimal fitting flat must pass through the mean of the point set?
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.
Project clustering is a natural generalization of k-...
0
votes
0answers
70 views
Trade-off between number of spheres and wasted space in covering a 3d object by spheres
Consider the following optimization problem:
Input: a 3-dimensional "object" $O$.
Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
0
votes
0answers
211 views
Clustering in sublinear time/query
Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:
1) Minimizing the number of balls that are required to cover all ...
0
votes
0answers
437 views
Rectangular constraints in Delaunay Triangulation without edges within
I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...
0
votes
1answer
80 views
Algorithms to classify the geometrical relationship of two 3D-geometries
I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if
volume A is inside ...
