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

271 questions
Filter by
Sorted by
Tagged with
550 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 ...
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 ...
• 21.6k
493 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 ...
• 51
900 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 ...
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$, ...
• 6,033
206 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 ...
• 409
991 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 ...
287 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 ...
• 23.1k
459 views

### Optimizing $\epsilon$ in $\epsilon$-kernel

The notion of $\epsilon$-kernel, as defined by Agarwal et al. ("Approximating extent measures of points"), is the following. Let $S^{d−1}$ denote the unit sphere centered at the origin in $R^d$. For ...
• 763
492 views

### Consequences of lower bounds for $\epsilon$-nets on approximation

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
• 2,613
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....
• 43
549 views

### Average distortion embeddings

Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$. Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to ...
• 32.1k
320 views

### Linear Time Maximum Clearance Computation on a Grid Graph?

I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles. My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set. In other words, ...
• 151
803 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 ...
• 1,631
404 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?
• 6,033
438 views

### Lower bounds for linear satisfiability problem

In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
• 1,955
491 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)$ ...
• 9,870
353 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,...
• 9,626
350 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$, ...
• 12k
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 ...
• 2,613