# Questions tagged [computational-geometry]

The tag has no usage guidance.

98 questions
Filter by
Sorted by
Tagged with
71 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 ...
31 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 ...
80 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}\...
61 views

### Example of Delaunay Triangulation where it does not minimize the maximum angle

I know that that the Delaunay triangulation maximizes the minimum angle of triangulation. And it does not minimize the maximum angle. If we consider the set of points in general position(no four ...
34 views

### Delaunay Triangulaition (or Voronoi) for a specific distribution of points

I found a paper about Delaunay triangulation for a set of points that are distributed by the Poisson distribution (https://pdfs.semanticscholar.org/9693/4b7e8e5483893f4874d7ba6afd812bbfe0ba.pdf). The ...
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 ...
97 views

### How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to ...
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 ...
65 views

### Data structures for embedded simplicial complexes

I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
134 views

### The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
137 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. ...
44 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}$ -...
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? ...
72 views

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 ...
75 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 ...
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 ...
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 ...
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$...
51 views

### Inclusion probability of irregularly shaped polygon

I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S. My task ...
52 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 ...
48 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 ...
38 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 ...
66 views

given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $... 2answers 130 views ### How to continue this algorithm? [closed] I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º). I have thought about ... 0answers 98 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 ... 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$... 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 ... 1answer 494 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 ... 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 ... 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 ... 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 ... 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 ... 1answer 55 views ### Finding sets of heavily intersecting objects, while minimizing their size [closed] Assume I have some array$a$of length$n$. If I place the elements contained in the array$a$into a$\sqrt{n} \times \sqrt{n}$matrix, then every row "intersects" with every column. That is, I ... 0answers 131 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 ... 1answer 212 views ### Intersection graphs of squares and rectangles Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)? 0answers 139 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\}$-... 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$, ... 0answers 88 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 ... 0answers 69 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 ... 0answers 124 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 ... 1answer 316 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'} \...
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 ...
Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. ...