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

28 questions
Filter by
Sorted by
Tagged with
4k 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 ...
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 ...
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 /...
2k 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 ...
2k views

### Cover a Concave Polygon with a minimum number of rectangles

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
209 views

### Finding a simple dual of a simple graph in some surface

Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph ...
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? ...
2k 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$, ...
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 ...
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 ...
578 views

### Incremental drawing of large graphs

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
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 ...
495 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 ...
1k views

### Finding the closest pair between two sets of points on the hypercube

Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-...
923 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)$ ...
830 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 ...
825 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$ ...
2k views

### Calculating the distance to the kth nearest neighbor for all points in the set

For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and ...
2k views

### Computing integer points on the circumference of a given circle

Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The ...
390 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 ...
110 views

### Minkowski decomposition of lattice point cloud

Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$. Is there any known result for the following problem? ...
348 views

### Testing boolean vectors orthogonality with fast query-time

Consider the following problems, Problem1: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$ TASK: preprocess INPUT in such a ...
137 views

### Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
477 views

### Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
2k views

### polygonal triangulation and 3-colorability

Lets define polygonal triangulation a triangulation which has a hamiltonian cycle. It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
1 vote
223 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 ...
1 vote
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 ...
Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ ...