# Questions tagged [computational-geometry]

The tag has no usage guidance.

103 questions
Filter by
Sorted by
Tagged with
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 ...
546 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 ...
590 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$...
248 views

219 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 ...
81 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 ...
211 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). ...
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}\...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
168 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 ...
68 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 ...
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 ...
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 ...
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? ...
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\}$-...
215 views

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 ... 1answer 334 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 ... 3answers 392 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 ... 1answer 147 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. ... 1answer 136 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 ... 1answer 159 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 ... 2answers 108 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 ... 4answers 261 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$, ... 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 ... 1answer 125 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 ... 2answers 191 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'$... 1answer 156 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 ... 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 ... 0answers 107 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 ... 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 ... 2answers 344 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 ... 1answer 366 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'} \...
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 ...