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
1
vote
1answer
72 views

Term for a correspondence of two point sets regarding their ordering in each dimension

Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of ...
-1
votes
1answer
417 views

comparing polyhedra (or even more specifically convex hulls) in d dimensions

Does anybody have information on whether the problem of determining whether 2 polyhedra in d dimensions are the same, is polynomial or NP-complete, if so? Thanks
1
vote
0answers
467 views

How to efficiently compute a bounding box of a 2D compact function support?

I've come to an interesting problem. Let's have a 2D scalar function F and make some assumptions on it: it has compact support (region where it is defined and non-zero) its support consists of at ...
2
votes
1answer
150 views

List the $k$-faces of an $n$-dimensional simplex

Suppose you are given an $n$-dimensional simplex S = [ 0 1 ... n ] which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $...
9
votes
1answer
625 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
282 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
244 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
337 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?
144
votes
2answers
19k 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
558 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
308 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
161 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
522 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
369 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
666 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
376 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
760 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
624 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
358 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
331 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
558 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
276 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
228 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
399 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
903 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
551 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
685 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
510 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
191 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
480 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
427 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
505 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 ...
43
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
434 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
831 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 ...