Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

4
votes
0answers
38 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: ...
0
votes
0answers
11 views

How to find the minimum bounding rectangle of a set of coplanar points in 3D? [on hold]

Given a point set $P = \{p_1, p_2, ..., p_n\}$ in 3D, I want to draw a rectangle that contains all the $p\in P$ with minimal area. Which algorithm fits this problem the best? I think it is related ...
12
votes
2answers
159 views
+150

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
22 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
33 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
25 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
40 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
24 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
63 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
17 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
25 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
45 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
43 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
6 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
15 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 ...
3
votes
0answers
15 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
69 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
65 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
104 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
22 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
88 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
48 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 ...
10
votes
1answer
151 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 ...
1
vote
1answer
131 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
59 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
53 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
124 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
86 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
229 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
144 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
49 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 ...
2
votes
0answers
26 views

In case of a given graph , Is that possible to build trapezoidal map in linear time

[This regarding to Computational geometry in CS] Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G). I'd like to build a trapezodial map out ...
6
votes
0answers
94 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
-2
votes
2answers
51 views

Efficient algorithm for extreme spread of points in a plane

Given a set $X$ of $n$ points in the real plane, designated by their Cartesian coordinates, find the extreme spread of the points, which is defined by $\qquad\displaystyle \mathrm{ES} = \max_{1 \leq ...
0
votes
0answers
16 views

Maximum amount of positional offset caused by noisy distance measurements in Quadrilateration

Quadrilateration is a range-based localization technique applied to wireless sensor networks. It is the equivalent method of trilateration in 2D. Assume that, there are four beacons (the sensors ...
0
votes
0answers
10 views

Is there any staticstics for the effect of noisy range measurements to the localization percentage in 3-D Range-based localization?

I'm implementing a simulation for 3D range-based wireless sensor network localization. In order to simulate the real-world cases, I need to impose some distance measurement errors. When I run my ...
0
votes
2answers
70 views

criterion for two line segments intersecting

I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect. My current algorithm tries the following: the line $[(x_1, y_1),(x_2, y_2)] ...
0
votes
0answers
21 views

Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
1
vote
1answer
27 views

Covering grid with constrained rectangles

I need to place N rects on a 2-dimensional grid with constraints. For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known. The problem is to place all rects on a grid ...
1
vote
0answers
20 views

Choose m points out of n that form the polytope with the maximum volume in hyperspace

Let's say I have a set $A$ of $n$ points represented by real vectors of length $l$. What type of algorithm would I use to find the subset $B$ of $m$ ($m$ is arbitrary, to be chosen) points that ...
7
votes
0answers
179 views

Testing whether a tetrahedron lies inside a Polyhedron

I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$. I would like to add one detail ...
2
votes
2answers
45 views

Partition area using test function

I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f ...
1
vote
0answers
40 views

Vertex pertubation along an edge and a triangle

I am trying to implement a mesh generation algorithm. Input to the algorithm is a set of constraints(imposed on output mesh) called Piecewise Linear Complex(PLC) which is a collection of vertices ...
4
votes
1answer
54 views

$O(n \log n)$ simple polygon triangulation via divide and conquer

I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon. It seems like there should be a simple divide and conquer variant that would fit the bill, ideally ...
7
votes
0answers
64 views

Is there an O(n log n) algorithm for 4D line simplification?

The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
2
votes
1answer
68 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
1
vote
0answers
29 views

Localizing a plane in 3-D using distance geometry

Assume that I have a set of coplanar points $P = \{p_1, p_2, ... , p_n\}$ The equation of the plane is unknown. $\forall p_i,p_j \in P$, pairwise euclidian distance $d(p_ip_j)$ is known. And I have ...
1
vote
0answers
26 views

How do you sketch a B-spline basis function?

I'm presented with the question on the practice exam: Sketch the curve and control points for the cubic B-spline basis function N^3_2 over the knot sequence with 8 knots, full multiplicity at ...
2
votes
0answers
71 views

Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V$ and a set of segments $S$. I want to know whether a segment in the set $S$ is Delaunay against the vertices in $V$. I would like to state my assumed definition of a ...
3
votes
2answers
69 views

Fast algorithm to find points on one side of hyperplane?

Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm (1) Preparation: first take the n points as an input, ...