Questions tagged [computational-geometry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
17
votes
1answer
496 views

How not to compute the smallest circle enclosing a finite set of circles

Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of ...
12
votes
1answer
564 views

Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
11
votes
1answer
247 views

Compute lowest dimensional polytope from a given set of sign vectors

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\...
11
votes
1answer
302 views

Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
10
votes
1answer
156 views

Largest cell in an arrangement

Q. What is the complexity of finding the largest volume bounded cell in an arrangment of $n$ hyperplanes in dimension $d$? I feel I should know this... But I am not finding a definitive reference. ...
10
votes
1answer
136 views

Minimum equidecomposable decomposition

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$...
10
votes
0answers
132 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 ...
7
votes
1answer
152 views

Reference request: Shortest homotopic curve via vertex releases

Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic ...
6
votes
2answers
495 views

Would a purely topological computational model be useful in decision problems in topology?

If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
6
votes
1answer
121 views

Maximum number of geometrically disjoint paths - is the complexity known?

Let $G$ be an undirected graph, given with a planar drawing. We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct ...
6
votes
1answer
146 views

Embedding points in Euclidean space into a box

If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their ...
5
votes
2answers
210 views

Voronoi Diagram of Lines

Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(...
5
votes
2answers
203 views

Fast high-dimensional K-nearest neighbors

I'm aware of this question https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm But it's not the same question as I'm asking. Because, Octree and its generalization are only ...
5
votes
1answer
76 views

Complexity of computing the union of H-polytopes in three dimensions

Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex). We are also given a target ...
5
votes
3answers
209 views

Locating a point inside a union of simple polygons

I have a set of polygons (convex, concave – non-convex, not self-intersecting) in a plane. There may be intersections between polygons. Polygon is defined by points (cartesian coordinate system). ...
5
votes
0answers
81 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
70 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
51 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
106 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
264 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
72 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
1answer
182 views

Configurations from arrangement of lines

Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the ...
4
votes
1answer
161 views

Complexity of counting maximum number of co-linear points in Euclidean plane

The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points. I already know that the problem can be solved in quadratic time using hashing or projective ...
4
votes
1answer
66 views

Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke. In chapter 10 (pdf available on the above site), section 10.2.2. he shows ...
4
votes
1answer
110 views

Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Roughly speaking, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain. The algorithm specifies splitting the edges ...
4
votes
1answer
114 views

Polytopes convex hull

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
4
votes
0answers
47 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
207 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
1answer
297 views

Does Approx Carathéodory's theorem implies dimensionality reduction

Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be ...
3
votes
3answers
379 views

Partitioning a set of 2d polygons into intersection-connected subsets

My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them. In other words I have a set of ...
3
votes
1answer
139 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
3
votes
1answer
130 views

Generalization of Beck's theorem

Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of ...
3
votes
1answer
140 views

Convex polygons inclusion relation

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
3
votes
2answers
103 views

Data structure for radial orderings of points on the plane

Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$. Consider shooting an ...
3
votes
4answers
247 views

Find the maximum subset contained by a ball of radius R

I am searching for the name of / literature to the algorithmic problem as follows: Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, ...
3
votes
1answer
56 views

Emptiness of complement of subspace arrangement

Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem? P.S.: It seems that this can be ...
3
votes
1answer
97 views

Select circle with given radius that contains most points

Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points. I tried solving ...
3
votes
2answers
189 views

Is this covering problem NP-hard?

Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ ...
3
votes
1answer
150 views

Range searching: what is $\epsilon$?

I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well ...
3
votes
0answers
70 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
106 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
2answers
324 views

Coreset and VC dimension

I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
2
votes
1answer
318 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
2
votes
1answer
140 views

A least sized partition of a set under a distance metric

What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows: Input: A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are ...
2
votes
1answer
74 views

Complexity for single-linkage clustering with max norm

Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} |x_i-...
2
votes
1answer
201 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
2
votes
1answer
99 views

Approximating the value of k in $k$-mean clustering problem

Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
2
votes
1answer
58 views

Finding a cell in an arrangement of simplices

My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are ...