Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

1
vote
0answers
21 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
3
votes
1answer
27 views

Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...
4
votes
0answers
20 views

Enumerating Polygonal Subdivisons

Let $P$ be a given polygon in $\mathbb{R}^{2}$ such that all the vertices lie on integral points $\mathbb{Z}^{2}$. An integral polygonal sub-divison of $P$ is a subdivison of $P$ into integral ...
3
votes
1answer
34 views

Lower bound for maxima on 2D plane

Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane. A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$. A point is called a maxima if no ...
11
votes
1answer
581 views

What is the use of finding minimum number of straight lines to cover a set of points?

There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D. Even though I have scanned many papers, none of ...
3
votes
0answers
38 views

Complexity of clustering lattice points

[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now! $\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional ...
3
votes
1answer
35 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
1
vote
1answer
49 views

Weighted closest-pair-of-points problem

I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well). I have two sets of points in the plane: $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and ...
5
votes
1answer
110 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
1
vote
0answers
36 views

How do you find the union of the the unit squares contained in a polygon?

The Problem: Suppose you have a simple polygon (edges don't cross). Find the union of of all 1x1 squares that fit in the polygon. To be clear, I am asking for the union of all points that are in ...
1
vote
1answer
26 views

Finding stabbing numbers for lines for a set of segments in the plane

So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the ...
0
votes
2answers
42 views

Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$

Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D. Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ ...
4
votes
1answer
67 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= ...
2
votes
0answers
18 views

Fast search of local positive quadruples on the sphere

[redirected from math.stackexchange.com] Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ ...
0
votes
0answers
65 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
1
vote
2answers
95 views

Determine whether a point lies in a convex hull of points in O(logn)

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one ...
1
vote
0answers
26 views

Modify one element and find out which surounding elements are affected

I want to know if there is an algorithm which does the following: Imagine you have a point cloud and the points affect each other but the action from each point to an other is only valid in some ...
0
votes
0answers
46 views

Data Structure implementation to store Sweep Line Status in Sweep Line Algorithms

I have been trying to implement the data structure for storing the sweep line status in sweep line algorithms (eg. Bentley-Ottmann for line segment intersection) and finding it difficult to implement ...
2
votes
0answers
46 views

Data Structure for storing the Sweep Line Status in Sweep Line Algorithms

I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree ...
2
votes
1answer
128 views

Finding the Best Fitting Plane Given a Set of 3D Points

Suppose that we have $n$ points in 3D. I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum. I read this article. However, I need an ...
0
votes
0answers
32 views

Polygon offset from two closed curves

Let $P$ be a simple polygon, let $\delta$ the minimum distance from any vertex $v$ of $P$ to any edge of $P$ that is not incident to $v$, and let $0 <\epsilon<\delta/2$. How can I prove that the ...
2
votes
1answer
45 views

Good data structure for finding all points in one set a distance from each point in another set

Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$. For each $x_i \in X$, I need to find all $y \in Y$ such that ...
2
votes
1answer
59 views

Constructing non intersecting segments from distinct sets of points

Given 2 sets of points in the plane, $A$ and $B$, each of size $n$, I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect. The ...
1
vote
0answers
29 views

n-point hull of a set of points

I ran into the following, deceptively simple problem, and I was wondering if there is a well-known algorithmic solution to it: Given a set of points $S$ in $\mathbb{R}^d$ (or $\mathbb{R}^2$, for ...
4
votes
0answers
57 views

Computing average tile size (grid)

I am trying to compute the average cell size on the following set of points, as seen on the picture: . The picture was generated using gnuplot: ...
15
votes
3answers
257 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
0
votes
1answer
64 views

Voronoi diagram algorithm with non-euclidean metric

Do you know any easy to implement algorithm for construction Voronoi diagram from given set of points on a surface, using some different metric (taxicab, for instance)? It can be some modification of ...
1
vote
0answers
84 views

Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
0
votes
1answer
92 views

Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of ...
1
vote
0answers
102 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
1
vote
0answers
26 views

Separate points inside set

I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ...
1
vote
1answer
89 views

Finding nearest of a list of points on Euclidian plane to a given reference point

Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$. ...
0
votes
0answers
25 views

Why we use Affine Spaces for transformations?

While studying about Affine transformations in Computer Graphics,I couldn't find any special reason for using Affine transformations because I think even if we use transformations in Vector Space we ...
3
votes
0answers
32 views

Fast and space efficient data structure for nearest neighbors in 3 dimensions?

I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ ...
3
votes
0answers
53 views

How fast is closest pair?

I'm reading a recent paper "Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem" by Gregory Valiant on finding approximate closest pairs in ...
1
vote
1answer
55 views

Minimizing total distance to a point from a set of points

I've read about a problem: There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal. I've written a Monte-Carlo algorithm, ...
1
vote
0answers
10 views

Modifying the Erroneous Pairwise Distances of 4 Points to Get Coplanarity

Consider four points $i,j,k,l$ and their pairwise Euclidiean distances $d(ij)$ $d(ik)$ $d(il)$ $d(jk)$ $d(jl)$ $d(kl)$ Say that, we know the coordinates of the points $j$, $k$ and $l$. However, we ...
1
vote
0answers
23 views

Disc covering problem

I have an arbitrary 2d area on the xy plane. I want to cover it with N discs such that all points in the area have at least one disc overlapping it. A disc with center (xc, yc) placed inside this area ...
0
votes
2answers
137 views

k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution ...
3
votes
0answers
19 views

Detecting coplanarity by given erroneous pairwise distances

This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now. Here, I summarize the original problem: We have points in 3D space. We do not ...
4
votes
0answers
77 views

Minimal covering circle

There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...
4
votes
2answers
90 views

Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
3
votes
1answer
171 views

Find point with smallest average distance to a set of given points

Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest): Given $n$ points $P_i=(x_i,y_i)$ in the 2-dimensional plane, find the point ...
0
votes
0answers
35 views

Algorithm to decompose self intersecting polygons

Suppose I have self-intersecting polygons as shown in image below (basically I have start and end points of the poly-lines of the polygons): Are there algorithms which will decompose such polygons ...
0
votes
2answers
97 views

Count points enclosed by several planes in 3D space

I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane can make regions, some of them closed, and others not, the task is to count the number of points ...
2
votes
0answers
50 views

Finding a convex hull for a collection of points

I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan. Find a point that is guaranteed to be ...
12
votes
2answers
238 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
2
votes
2answers
247 views

Divide self-intersecting polygon into simple polygons

My question is similar to question here Divide self-intersecting polygon I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects. I have to divide ...
1
vote
1answer
70 views

Feasible solution existence

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty. Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is ...
4
votes
1answer
60 views

Optimal Algorithm for Finding Maximal Number of Colinear Points

Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line). The crudest algorithm is to compute the slope and intercept of each ...