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
9
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
10
votes
1answer
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 ...
8
votes
1answer
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 ...
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 ...
4
votes
0answers
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?
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? ...
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 ...
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 ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
11
votes
4answers
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 ...
5
votes
2answers
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 ...
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 ...
5
votes
2answers
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 ...
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 ...
11
votes
1answer
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 ...
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-...
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....
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-...
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 >...
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 ...
4
votes
2answers
327 views

Find optimal room from which to visit all other rooms in a rectangular floorplan

Suppose we have an orthogonal polygon with holes (all walls are axis-parallel). All vertices can be on integer coordinates, if that helps. Partition the polygon into rectangular rooms. I would like ...
10
votes
0answers
345 views

Covering a set of intervals, continued

Peter Taylor and Tsuyoshi Ito solved a previous question that I posted: Covering a set of intervals I have a slight variation on that question that I'd also like to ask. I'm not sure what the ...
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 ...
8
votes
1answer
274 views

Partitioning a connected shape into rectangles

I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers ...
8
votes
1answer
227 views

What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)

This is a cross-post from MathOverflow. The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the Steinitz Problem. Sturmfels and ...
7
votes
4answers
394 views

Find all nearby points in a set, for each element of the set

Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's ...
5
votes
1answer
843 views

Covering a set of intervals

(I was redirected from mathoverflow in asking this) Hello, I'm trying to determine if the following problem is solvable in polynomial time: given a collection of $n$ half-open intervals $[s_i, t_i)$ ...
9
votes
3answers
2k views

Algorithms for Polygon triangulation

I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation. Can any one guide me to find published paper/algorithm, please? PS:...
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 ...
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 ...
8
votes
1answer
670 views

Is that particular case of the “minimum weight solution to linear equations” still NP-complete?

We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find ...
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 ...
1
vote
3answers
2k views

Sorting array of distances by proximity to each other

I was playing with geolocation on maps and stumbled on an interesting problem: I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes ...
4
votes
1answer
140 views

Process on finite points in a line

This is related to some old posts that were closed because someone had felt that they're related to homework. All I'm looking for here is a reference to a paper that may have partially or completely ...
7
votes
2answers
189 views

Geometric differencing

The diff procedure can be generalized to operate on objects other than strings. For instance, I imagine that computational geometry asks questions like: "Given two volumes, and allowed only the ...
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 ...
7
votes
1answer
285 views

Approximating convex sets

In the Haussdorf approximation of a convex object $C$ (and in much core-set work), the standard approach is to take an $\epsilon$-net on the enclosing hyper-sphere, then project it down to $C*(1 + \...
6
votes
1answer
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 ...
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 /...
8
votes
1answer
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 ...
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 ...
5
votes
3answers
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 ...
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 ...
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$, ...
3
votes
2answers
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 ...
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 ...
7
votes
2answers
286 views

Paths in a weighted line arrangement

This is a followup to my followup to David's question. This question admittedly leaves the original motivation far behind, but it might provide some useful intuition. Suppose we are given a set of n ...