As of May 31, 2023, we have updated our Code of Conduct.

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).

Filter by
Sorted by
Tagged with
2 votes
1 answer
92 views

Complexity of polygon intersection test

In the book "Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems)", there's a section on simple polygon intersection detection , and it mentions ...
Lieven's user avatar
  • 123
1 vote
0 answers
46 views

Diameter queries for stream of points

Given an online stream of $k$ points $x_1, x_2,\ldots,x_k$ with $x_i \in \mathbb{R}^2$. By online we mean that when $x_i$ arrives we have no knowledge of points $x_j$ for $j > i$. Denote by $S_i$ ...
NLR's user avatar
  • 11
0 votes
0 answers
94 views

Approximation algorithm for maximum independent set of squares

In the problem of maximum independent set of rectangles (MISR), there is a collection of axes-parallel rectangles, and the goal is to find a largest set of pairwise-disjoint rectangles. The latest ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
60 views

Partial linear spaces and partial projective planes

In 1948, De Bruijn and Erdős [1] proved that a finite linear space on $n$ points has at least $n$ lines, with equality occurring if and only if the space is either a near-pencil (all points but one ...
Cyriac Antony's user avatar
2 votes
2 answers
174 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-...
Niklas Rosencrantz's user avatar
1 vote
1 answer
97 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 ...
Neal Young's user avatar
  • 9,555
1 vote
1 answer
244 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 ...
Erick Weber's user avatar
2 votes
0 answers
43 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 ...
templatetypedef's user avatar
2 votes
2 answers
266 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 ...
Erel Segal-Halevi's user avatar
6 votes
2 answers
429 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. . ...
user3483902's user avatar
  • 1,081
12 votes
0 answers
354 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 ...
Andres Fuentes's user avatar
13 votes
0 answers
350 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 ...
asdfqwer's user avatar
4 votes
1 answer
158 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 $\...
M A's user avatar
  • 215
1 vote
1 answer
242 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⁡(...
amit's user avatar
  • 11
0 votes
1 answer
75 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 ...
Mohammad Al-Turkistany's user avatar
4 votes
1 answer
153 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$. ...
Elliot Gorokhovsky's user avatar
4 votes
0 answers
96 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\...
Thomas Ahle's user avatar
3 votes
0 answers
606 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 ...
user1494080's user avatar
7 votes
1 answer
193 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 ...
Jérôme Verstrynge's user avatar
9 votes
0 answers
156 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 ...
Falk Hüffner's user avatar
3 votes
1 answer
139 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 ...
Mohammad Al-Turkistany's user avatar
9 votes
1 answer
316 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$ ...
mhum's user avatar
  • 3,382
3 votes
0 answers
91 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 ...
Simd's user avatar
  • 3,940
3 votes
0 answers
80 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 $ |...
Elliot Gorokhovsky's user avatar
7 votes
1 answer
176 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 ...
Gabriel Nivasch's user avatar
2 votes
0 answers
66 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 ...
Matteo's user avatar
  • 43
2 votes
0 answers
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 ...
Hung Le's user avatar
  • 305
17 votes
1 answer
596 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 ...
Robin Houston's user avatar
9 votes
0 answers
357 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 (...
pimlu's user avatar
  • 91
2 votes
0 answers
105 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 \...
Minwei Ye's user avatar
3 votes
1 answer
454 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 ...
saul.shanabrook's user avatar
4 votes
0 answers
148 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\}$-...
FiB's user avatar
  • 141
11 votes
1 answer
256 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 ...
GMB's user avatar
  • 2,333
5 votes
1 answer
165 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 ...
S. Pek's user avatar
  • 423
12 votes
1 answer
342 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 ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
232 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 ...
Kapoios's user avatar
  • 161
6 votes
1 answer
337 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 ...
Erel Segal-Halevi's user avatar
4 votes
0 answers
112 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? ...
Bruno's user avatar
  • 4,440
11 votes
1 answer
249 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\...
Holger's user avatar
  • 975
4 votes
1 answer
121 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 ...
Adi Shavit's user avatar
1 vote
1 answer
68 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 ...
Thomas Ahle's user avatar
-2 votes
1 answer
90 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 ...
Yan Zhu's user avatar
  • 101
0 votes
1 answer
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 ...
Daniel's user avatar
  • 749
3 votes
1 answer
410 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") ...
Ecir Hana's user avatar
  • 289
4 votes
1 answer
196 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 ...
Mikola's user avatar
  • 581
1 vote
0 answers
86 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 $$ $...
Daniel's user avatar
  • 749
4 votes
0 answers
140 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$...
Mikola's user avatar
  • 581
5 votes
2 answers
247 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 ...
AmeerJ's user avatar
  • 679
3 votes
0 answers
123 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$...
Untitled's user avatar
  • 191
4 votes
0 answers
174 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 ...
Quanquan Liu's user avatar

1
2 3 4 5 6