# Tagged Questions

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

136 views

### Complexity of union (computational geometry)

I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars and found the following theorem 13.9. Let $S$ be a collection of convex polygonal ...
91 views

3k views

### An algorithm to efficiently draw a extremely large graph in real time

Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime I was ...
352 views

### Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different ...
259 views

### Placing points far away from each other in simple polygon

I am sure the following problem has been studied before, but I did not find any literature about it. ...
197 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 ...
653 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$ ...
454 views

### Learning triangles in the plane

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
1k 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 ...
444 views

### Drawing graphs with few “sharp” vertices?

For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other ...
135 views

### Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ ...
205 views

### Counting the number of thick regions which overlap a square

Let $S$ be a unit square. As a function of $\beta$, what is the maximum number of $\beta$-fat pairwise-disjoint regions with diameter at least 1 which can intersect $S$? Below, we give a figure ...
981 views

### Polygon within polygon generalization problem

I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical ...
2k views

### VC-dimension of spheres in 3 dimension

I am searching for the VC-dimension of the following set system. Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ ...
917 views

### Dynamic Upper Envelope of lines in the plane

There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey Davenport-Schinzel sequences and their geometric applications. ...
173 views

### Triangulation with maximum greatest area

Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define $$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$ which denotes the series of interior angles of $T$, ...
899 views

### Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
411 views

### Cheapest dissection of a grid polygon into rectangles with cost

My problem: Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.) The rectangles must be taken from a predefined set (which ...
285 views

### Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

I'm trying to find a solution for the following problem. You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and ...
165 views

### Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
106 views

### Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes: Is there an algorithm that enumerates the ...
257 views

### Is the cutting lemma true with O(r) lines?

The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the ...