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
143
votes
2answers
18k views

Super Mario Galaxy problem

Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop? ...
52
votes
1answer
1k views

A combinatorial version for the polynomial Hirsch conjecture

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
42
votes
3answers
3k views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
37
votes
6answers
2k views

Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover). Does anyone know of a problem ...
37
votes
3answers
2k views

Parameterized complexity of Hitting Set in finite VC-dimension

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
28
votes
17answers
2k views

Examples where insight from geometry was useful for solving something completely non-geometric

One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think ...
27
votes
1answer
2k views

Isometric embedding of L2 into L1

It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$. Is ...
25
votes
1answer
534 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
23
votes
5answers
2k views

Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
23
votes
3answers
724 views

Convex Body with minimum expected l2 norm

Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...
22
votes
2answers
2k views

Detecting two kinds of almost-simple polygons

I'm interested in the complexity of deciding whether a given non-simple polygon is almost simple, in either of two different formal senses: weakly simple or non-self-crossing. Since these terms are ...
22
votes
1answer
1k views

Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
21
votes
1answer
1k views

Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, ...
20
votes
6answers
3k views

Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
19
votes
2answers
1k views

A data structure for minimum dot product queries

Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
18
votes
1answer
3k views

The quad-edge data structure (Delaunay/Voronoi)

2 questions for the computational geometers or algebraists: I am just beginning to dive into computational geometry and I am loving it =) I am attempting to read the famous article by Guibas and ...
18
votes
2answers
731 views

Find a largest cube contained in the union of cuboids

I have a lot of cuboids in 3D space, each has a starting point at (x,y,z) and has size of (Lx,Ly,Lz). I wonder how to find a largest cube in this 3D space that is contained in the union of the cuboids....
17
votes
3answers
487 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 ...
17
votes
2answers
1k views

Sorting by Euclidean distance

$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$. A no-brain approach is to ...
17
votes
1answer
545 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 ...
17
votes
0answers
354 views

complexity of checking if a subspace is a Euclidean section of L1

If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have $(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$ for some small $\epsilon >...
16
votes
2answers
465 views

Finding the largest set of points of limited diameter

Given points $p_1,\ldots,p_n$ in $\mathbb{R}^{d}$ and a distance $l$ find the largest subset of these points such that the Euclidian distance of no two of them exceeds $l$. What is the complexity of ...
15
votes
1answer
363 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
15
votes
1answer
784 views

Is the lower bound proof in this paper correct?

In this paper on "Circle Packing for Origami Design Is Hard" by Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, on page 15, figure 13, they claim that the side length of the smallest square that ...
15
votes
1answer
507 views

Drawing graphs with few “sharp” vertices?

For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other ...
15
votes
1answer
366 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?
14
votes
6answers
554 views

Planar graph via the intersection of fat thingies?

There is a beautiful theorem of Koebe (see here) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be ...
14
votes
2answers
585 views

The number of triangulations of a set of $n$ planar points: Why so difficult?

After hearing Emo Welzl speak on the subject this summer, I know the number of of triangulations of a set of $n$ points in the plane is somewhere between about $\Omega(8.48^n)$ and $O(30^n)$. ...
14
votes
3answers
389 views

Separation of a preprocessed polyhedron and a plane

I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/...
14
votes
1answer
740 views

Computing the Löwner-John ellipsoid of a polyhedron

The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations ...
14
votes
0answers
371 views

Applications of fat shattering dimension in computational geometry

The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-...
13
votes
2answers
413 views

Best way to determine the minimum dimension of a structure given only distances between points

I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it ...
13
votes
2answers
491 views

Learning triangles in the plane

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
13
votes
2answers
777 views

Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time

Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do ...
13
votes
2answers
598 views

Estimating VC-Dimension

What is known about the following problem? Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-...
13
votes
1answer
302 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,...
13
votes
1answer
416 views

Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

Are there any problems that are NP-complete when using Euclidean geometry but are well-defined and solvable in polynomial time for some non-euclidean geometry?
13
votes
2answers
380 views

Data structure for updates on intervals and querying number of zeros

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$. $\text{increase}(a,b)$, which increases $t[a],t[a+1],...
13
votes
0answers
323 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 ...
13
votes
0answers
404 views

Exact nearest neighbor in $d$-dimensional Euclidean space

Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \...
12
votes
6answers
770 views

What is a really good problem to get your hands dirty in computational-geometry?

Computational geometry is an area I find pretty interesting, and I'd like to devote about a month or two to a project that will introduce me to this and help me learn key concepts. What is a good way ...
12
votes
2answers
557 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 ...
12
votes
5answers
444 views

Motivation for volume estimation

What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods? These papers on volume ...
12
votes
3answers
340 views

Complexity of Localization in Wireless Networks

Let distinct points $1 ... n$ sit in $\mathbb{R}^2$. We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, ...
12
votes
1answer
336 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 ...
12
votes
0answers
330 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 ...
11
votes
4answers
484 views

Dimensionality reduction with slack?

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
11
votes
1answer
784 views

Finding a dual of a graph

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ ...
11
votes
1answer
228 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 ...
11
votes
2answers
268 views

Art gallery variants with pairwise visibility?

The traditional art gallery problem sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region. Has anyone ...

1
2 3 4 5 6