Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
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 ...
6
votes
1answer
91 views

Hidden constant in eps-sample size computation

Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\...
7
votes
2answers
3k views

VC dimension of polynomials (in one variable) of degree d

Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$. I am searching for ideas that can prove the ...
5
votes
0answers
360 views

Strongly edge-guarding a 3d triangulation

Let $T$ be a planar triangulation. It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and ...
4
votes
0answers
172 views

Approximation ratio for covering n points in d dimensions

What is best known approximation ratio for the following problem : Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a ...
10
votes
1answer
129 views

Longest edge length of the greedy spanner on uniformly distributed pointsets in $[0,1]^d$

Let $P$ be a set of $N$ points in $\mathbb{R}^d$. For any $t \geq 1$, a $t$-spanner is an undirected graph $G=(P, E)$ weighted under the Euclidian measure, such that for any two points $v$, $u$, the ...
2
votes
2answers
160 views

Maximum Crossing number of topological graph

The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane. Is there anything known about the maximum number of ...
1
vote
0answers
127 views

Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D [closed]

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
0
votes
0answers
416 views

Identify all of the non-overlapping rectangular regions of a simple concave polygon

I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will ...
0
votes
0answers
472 views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
11
votes
2answers
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 ...
7
votes
2answers
192 views

Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of ...
3
votes
3answers
368 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 ...
5
votes
0answers
328 views

Examples of simple charging schemes

I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope ...
14
votes
1answer
335 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
1
vote
1answer
844 views

Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?

An elaboration on this question, but with more constraints. The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
2
votes
0answers
74 views

Connectivity keeping centralized algorithm for multi-agent network navigation

We have a network of $N$ agents moving in a field. Every agent has communication bandwidth of range $R$. During the process we must keep all-to-all communication among the agents. So we have ...
9
votes
1answer
381 views

Algorithm for approximating convex bodies by a convex hull of ellipsoids

I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $...
6
votes
1answer
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 ...
9
votes
1answer
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 ...
7
votes
1answer
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. ...
5
votes
1answer
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 ...
10
votes
1answer
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$ ...
13
votes
2answers
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$ ...
22
votes
2answers
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 ...
15
votes
1answer
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 ...
4
votes
1answer
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$ ...
9
votes
1answer
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 ...
9
votes
2answers
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 ...
9
votes
2answers
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}$ ...
8
votes
2answers
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. ...
4
votes
0answers
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$, ...
1
vote
1answer
899 views

Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
6
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
165 views

Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
8
votes
0answers
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 ...
8
votes
2answers
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 ...
5
votes
3answers
363 views

What defines a “decent” polygon?

Acknowledgments/apologies (Feb 10). Thanks to those who have taken the time of reading this question and trying to find an answer (I've upvoted the three answers so far). I hope that after some ...
2
votes
0answers
141 views

Best known results pairwise distance computation of high-dimensional points?

Suppose we are given a family $F$ of $n$ sets of total cardinality $N$ with elements of the sets drawn from a universe $U$ of size $|U| = d$. Alternately, suppose we have $n$ points in $R^d$, or $n$ $...
6
votes
0answers
302 views

Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
6
votes
1answer
341 views

Solving multiple instances of 3SUM generated from the same set

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM) Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ ...
9
votes
2answers
166 views

Tradeoff Bounds for Halfspace Range Counting

What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff. According to Matousek's seminal 1993 ...
8
votes
1answer
461 views

Die roll problem

Edit: I think the spirit of the question was good, but it needs to be improved. The assumptions made for the coin toss made that question trivial, and the die roll is still not precisely defined ...
11
votes
3answers
2k views

Find Shortest Pairwise Distance of Points in o(n log n)?

The following exercise has been handed out to students I supervise: Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of ...
7
votes
1answer
198 views

Voronoi diagram on surface of polyhedron

Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface? I am particularly interested in convex ...
6
votes
3answers
486 views

How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring ...
2
votes
2answers
379 views

NP-hard problem on planar unit disk graph

I am curious to know whether there are problems which are np-hard even on planar unit disk graphs. A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we ...
23
votes
3answers
699 views

Convex Body with minimum expected l2 norm

Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...
9
votes
1answer
1k views

Computing volume of high-dimensional convex polyhedra

I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-...