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

270 questions
Filter by
Sorted by
Tagged with
66 views

### References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
127 views

### Fixed orientation metrics

I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively. The fact is as follows: Given ...
177 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 ...
404 views

### Triangulating a Planar Polygon

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
1 vote
50 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$ ...
352 views

### Reference to lower bound on separator in a grid?

It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane,...
65 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 ...
667 views

### Small $\epsilon$-nets for points and half-planes without VC dimension

I have recently learned the proof of Haussler and Welzl of the following theorem. Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
641 views

### Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results. Specifically, I'm interested in seeing some hardness proofs for problems that are ...
1k views

### What is the problem in "closest pair problem" if all points share the same x-coordinate

The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large ...
2k views

### VC dimension of intersection of half-spaces

Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$ for $i=1,...,n$, where $x \in \mathbb{R}^d$. Then define the classifier $$g(x) := \max \{ l_1(x),..., l_n(x) \}$$ which represents ...
1 vote
134 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 ...
308 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-...
1 vote
267 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 ...
54 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 ...
281 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 ...
458 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. . ...
356 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 ...
146 views

### (eps,delta)-approx with VC-Dimension 1?

I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all ...
359 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 ...
164 views

3k views

252 views

### Places where the order of points along a simple polygon passing through them is useful

We know that finding the convex hull of $n$ points on a plane has a lower bound of $\Omega(n\log n)$ on its running time. However, if the points are given in the order in which they occur along some ...
180 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 ...
353 views

### Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$. My assumed ...
342 views

### Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., ...
320 views

### Linear Time Maximum Clearance Computation on a Grid Graph?

I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles. My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set. In other words, ...
542 views

### Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
348 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 ...
601 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 ...
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 ...
433 views

### VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
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 ...