# Questions tagged [computational-geometry]

The tag has no usage guidance.

123 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Placing a circle in a point cloud

I need to place a circle with fixed radius in a cloud of points. The circle also must lay in a polygon (the points are also in that polygon) This circle has to contain as many points as possible. Are ...
• 11
44 views

### Affine point matching in general dimensions

Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
• 131
89 views

### Complexity of finding a room-partitioning

In a paper by Jack Edmonds and Laura Sanità (link: https://www.sciencedirect.com/science/article/pii/S1571065310001605) the following intriguing result is given: Given a triangulation $T$ of $3n$ ...
• 1,336
85 views

### Enforcing general position in $2d$ linear programming

Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$. I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
• 1,153
43 views

### Geometric Set Cover Problem and Union Complexity

I have encountered an instance of the Geometric Set Cover problem where the complexity of the union of any subset with size, say k, of m objects is linear with respect to m. I am aware of a well-known ...
68 views

### kd-tree optimality for orthogonal range search

It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
• 1,177
21 views

### Intersection of cuttings with a new hyperplane in d dimensions

Consider a d dimensional space with $n$ hyperplanes in general position. Based on these hyperplanes $n/r$ cuttings are constructed. If a new hyperplane is given, how many of the $d$-simplices from the ...
• 38
1 vote
55 views

107 views

### Finding planes from their points

Given some points $P=\{x_1,\dots,x_m\}$ in a vector space $(Z/2Z)^n$, if $P$ is a union of linear subspaces all of the same dimension $1<d<n$, can we efficiently find these subspaces? (Any ...
• 4,485
308 views

### A problem in understanding an algorithm

I read a paper from John Hershberger with this title: "Minimizing the sum of diameters efficiently". That paper proposed a simple algorithm that finds a bipartition of points $S$ in the ...
• 210
1 vote
71 views

### How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
• 119
93 views

### Complexity of detecting general position in the plane?

What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let'...
• 10.8k
116 views

### A counter example for the set mean objective

Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function \begin{align} cost(\mathcal{P},c) =...
• 265
79 views

### "Fast" approximation algorithm for geometric hitting set of same-height rectangles

In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects. ...
• 2,153
34 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 ...
• 5,656
101 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. ...
189 views

### How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
468 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 ...
• 5,127
43 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. ...
• 137
68 views

### Find a boundary from set of 3d line segments

I have a set of n 3d line segments ...
• 189
93 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,656
1 vote
46 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 ...
• 2,252
94 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}\...
393 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 ...
• 1,531
76 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,656
276 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 ...
• 123
235 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 ...
• 41
138 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 ...
• 215
1 vote
170 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
• 1,079
249 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. ...
• 885
52 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}$ -...
• 11
55 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? ...
• 10.6k
1 vote
115 views

• 21
511 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 ...
1 vote
80 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,002
152 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 ...
• 107
73 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 ...