Questions tagged [cg.comp-geom]
Computational Geometry is the study of geometric problems from a computational perspective. Examples of problems include: computation of geometric objects such as convex hulls, dimensionality reduction, shortest path problems in metric spaces, or finding a small subset of points that approximates some measure of the whole set (i.e. a coreset).
267
questions
2
votes
2answers
105 views
Status of certain problems in knot theory
I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
2
votes
1answer
41 views
partitioning points in the plane into two clusters to minimize maximum cluster diameter
What is a fast algorithm for the following problem?
input: a set of $n$ pairs of points in the Euclidean plane
output: a partition of the points into two clusters so that, for each given pair, the ...
1
vote
1answer
203 views
Is this a novel technique for determining whether or not two rotated rectangles collide?
I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm:
Rotate both rectangles by the negative rotation ...
2
votes
0answers
30 views
Efficiency of building orthogonal range search structures?
I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but ...
2
votes
2answers
129 views
Partitioning a connected polygon into connected pieces of equal area
Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same ...
6
votes
2answers
382 views
Complexity of Unknotting problems
The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references:
The Computational Complexity of Knot Problems.
Knottedness is in NP, modulo GRH. .
...
12
votes
0answers
340 views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
13
votes
0answers
331 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed]
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
4
votes
1answer
146 views
Minimizing $L_2$ norm of a vector with two distinct entries
Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values.
Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\...
1
vote
1answer
117 views
VC-dimension of infinite set of triangle wave
I am searching for the VC-dimension of the following:
What is the VC-dimension of the infinite set of triangle wave functions with
amplitude 1 and period parameter p on points on the line?
2πarcsin(...
0
votes
1answer
59 views
How hard is deciding the existence of a polygonization with prescribed perimeter?
Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
asked Nov 21 '20 at 15:48
Mohammad Al-Turkistany
20.4k4 gold badges57 silver badges144 bronze badges
4
votes
1answer
133 views
Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?
I need to use the following well-known result in my paper:
Let $X$ be a set of $n$ points in $\mathbb{R}^d$. Then $(X,\ell_2^d)$ embeds isometrically in $\ell_p^\binom{n}{2}$ for all $p \geq 1$.
...
4
votes
0answers
87 views
Can we make Tensor Sketch any faster?
For all constants $\epsilon,\delta>0$, let $k=\epsilon^{-2}\log1/\delta$. We know there exists a linear transformation $M : \mathbb R^{k^2}\to \mathbb R^{\tilde O(k)}$, such that for all $x\in\...
2
votes
0answers
508 views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
7
votes
1answer
189 views
Document references describing weaknesses for cutting planes and algebraic proof system?
Here, Fortnow says (section 4.3):
Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on ...
9
votes
0answers
150 views
Optimal bee swarm plots: NP-hard?
Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with ...
3
votes
1answer
134 views
Complexity of existence of simple polygonalization with prescribed area?
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
9
votes
1answer
260 views
Proof for Upper Bound of Sum of Square Roots Problem
In [1], Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP.
Given integers $a_1, a_2, \ldots, a_n$ ...
3
votes
0answers
74 views
Data structure to report points in the intersection of two circles
The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly.
This was solved beautifully ...
3
votes
0answers
77 views
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
7
votes
1answer
165 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 ...
2
votes
0answers
62 views
Finding the largest set of points of limited diameter (2)
Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between ...
2
votes
0answers
53 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 ...
17
votes
1answer
558 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 ...
9
votes
0answers
349 views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
2
votes
0answers
101 views
Minimize the product of distances from n fixed points
Given $n$ fixed points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem:
$$
\begin{align}
\text{mininize} \ \ \ &\prod_{i=1}^n \...
3
votes
1answer
366 views
What is the proof that visibility graphs can be used to compute the shortest path?
I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying ...
4
votes
0answers
141 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\}$-...
11
votes
1answer
234 views
Smallest axis-aligned box that contains $k$ points
Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.
Output: The smallest volume axis-aligned bounding box that contains at least $k$ of these $n$ points.
I'm wondering if any ...
5
votes
1answer
152 views
Generalized Priority Queues
I was wondering if there is any literature on the following problem:
Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations:
Insert ...
12
votes
1answer
339 views
Partitioning a rectangle without harming inner rectangles
$C$ is an axis-parallel rectangle.
$C_1,\dots,C_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C_1\cup\dots\cup C_n \subsetneq C$, like this:
A rectangle-preserving partition ...
1
vote
0answers
186 views
Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices
I found an algorithm for constructing an $\epsilon$-net for a positive semidefine matrix $A\in[-1,1]^{n\times n}$ which has $rank(A)=d$, described in the paper
The approximate rank of a matrix and ...
6
votes
1answer
317 views
Largest rectangle not touching any rock in a square field
Following this mathematical question, I am interested in the algorithmic question:
Given $n$ points in the unit square,
find the largest area of an axis-parallel rectangle in the unit square
...
4
votes
0answers
108 views
Minkowski decomposition of lattice point cloud
Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$.
Is there any known result for the following problem?
...
11
votes
1answer
248 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\...
4
votes
1answer
111 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 ...
1
vote
1answer
66 views
Far point queries in high dimensions
Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".
This is ...
-2
votes
1answer
79 views
arbitrary segment stabbing query for 2d segments
Store a set of 2d segments S in some data structure. For an arbitrary query 2d segment q, answer a yes/no question in sublinear time: whether q intersect with any segment in S?
If the query is a ...
0
votes
1answer
3k views
VC-dimension of triangles in 2D space [closed]
I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7.
The issue is that, for the case when 4 points lying on a straight line ...
3
votes
1answer
371 views
Sorted intervals query
I'm in search for a data structure which efficiently operates over closed intervals with the following properties:
dynamically add or remove an interval
set, and anytime change, a number ("depth") ...
4
votes
1answer
182 views
Algorithm to find all intersections in set of simplices
What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?
In the ...
1
vote
0answers
80 views
k closest points that belong to a set
This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind.
I have a set of real vectors:
$$
S = \lbrace v_1, \dots, v_n \rbrace
$$
$...
4
votes
0answers
101 views
Bichromatic all nearest neighbors
Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where:
$f(r) = \text{argmin}_{b \in B} |r - b|$
That is $f(r)$ is the closest point in $B$ to the point $r$...
5
votes
2answers
220 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 ...
3
votes
0answers
102 views
$k$th closest pair of points
The problem of finding the pair of closest points in a set of points has been a classical example of divide and conquer technique for some decades now. But I could not find any results on finding $k$...
4
votes
0answers
170 views
Problems in dynamic algorithms in computational geometry
The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as:
Dynamic ...
3
votes
1answer
701 views
Time complexity of d-dimensional convex hull
Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of ...
1
vote
0answers
103 views
Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?
I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure.
This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of ...
5
votes
1answer
231 views
Number of points on the interior of the convex hull of a random subset
This question is in regards to the following problem:
Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally ...
3
votes
1answer
124 views
Find all hyperplanes separating unique sets of `k` points
I have a series of n points in d-dimensional continuous space. I want to find a series of hyperplanes such that ...
