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

263 questions
Filter by
Sorted by
Tagged with
607 views

### Euclidean Capacitated Facility Location Problem

In the Capacitated Facility Location Problem (CFLP), we are given a set of clients $C$ and a set of potential facilities $F$. Each client $j \in C$ has a demand $d_j$ that must be served by one or ...
1k views

### Compare similar N-Dimensional vector in a database

I want to compute Euclidian distance between similar vectors in a database (SQLite). So each column in the database is a value from my vector. The first problem appears, I have a large number of ...
278 views

### Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory

I have asked similar questions on stackoverflow; as i couldn't post the very same question in this part of stackexchange. However, i would still like to receive recommendations / advice from this ...
238 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 ...
331 views

### How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d?

An $\varepsilon$-net for a range space $(X,\mathcal{R})$ is a subset $N$ of $X$ such that $N\cap R$ is nonempty for all $R\in \mathcal{R}$ such that $|X\cap R| \ge \varepsilon |X|$. Given a range ...
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 ...
253 views

### Open problems on epsilon nets

What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?
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? ...
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 ...
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 ...
304 views

### Is there a local variant of TSP?

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take. It's likely NP-hard, I was just wondering if ...
158 views

### Size of BSP tree for a simple polygon?

Is there a known bound on the size of a BSP tree for a simple polygon? I am aware of the result by Toth which gives a tight $\Theta(n \log(n) / \log(\log(n)) )$ bound on the size of a BSP consisting ...
377 views

### Recovering the slope of a digitized line

Has there been any work on recovering the slope of a line segment from its digitization? One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized ...
515 views

### Graph planar drawing, with each edge's length is known

Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not. Further assume that this is a graph that can be embedded ...
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 ...
352 views

### Construction of graph embeddings with non-intersecting edges

I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this ...
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 ...
664 views

### Closure under Minkowski sum.

The Minkowski sum of two sets of vectors $A, B \in R^d$ is given by $$A \oplus B = \{ a + b \mid a \in A, b \in B \}$$ I just heard an interesting problem (attributed to Dan Halperin): Given a ...
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-...
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....
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-...
354 views

421 views

### Maximum ball transform

Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.) A ball in $f$ is a set of ...
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 /...
489 views

### VC-dimension of Cylinders within a Cylinder

I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows: $X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$ The ranges in $\mathcal{R}$ are formed by ...
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 ...
418 views

### Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$ s.t. $n \ge 1$ and $x$ in some feasible region The decision variables are $x$ (a vector) and $n$ (a scalar). How is this type of ...
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 ...
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$, ...
205 views

### Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants

This question has been asked at StackOverflow ( a variant of this has been asked at Math SE), but so far there is no great response. So I'm going to reask here-- with a bit of twist. I have a few ...