Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

3
votes
0answers
33 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
26 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
43 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
104 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
32 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
17 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
39 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
62 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
17 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
61 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 ...
0
votes
2answers
63 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
25 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
31 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
42 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
100 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
43 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
28 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
56 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
256 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
54 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
80 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
79 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
95 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
85 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
30 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
51 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
51 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
21 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
128 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
75 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
87 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
165 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
33 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
93 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
49 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
1answer
215 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
241 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
69 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
59 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 ...
3
votes
2answers
159 views

Quickly locating nearest rectangle from a point

The problem is as follows: There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the ...
0
votes
1answer
138 views

Calculate winding number

How can one calculate the winding number of a polygon given as a list of vertices in some (counter-clockwise or clockwise) order? The complexity of the algorithm must be linear time.
7
votes
4answers
239 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
6
votes
4answers
151 views

Detecting coplanarity by given pairwise distances

Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that ...
1
vote
1answer
60 views

How “coplanar” is a set of points?

Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to ...