Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

4
votes
2answers
231 views

Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that: ...
2
votes
1answer
14 views

Is there a general-case sweep line algorithm for line segment intersection?

I'm looking for a sweep line algorithm for finding all intersections in a set of line segments that doesn't necessarily respects the general position constraint of Bentley-Ottman's algorithm (taken ...
1
vote
0answers
22 views

Determine inner angles of twisted polygon

Is there any way to determine inner angle of twisted polygon? (Here's a picture of "normal" and "twisted" polygon ...
3
votes
1answer
255 views

Possible to connect arbitrary number of dots without intersections?

A (now closed) question on SO made me think about the following problem: Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point ...
5
votes
1answer
41 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their ...
1
vote
1answer
35 views

Why are the two farthest points vertices of the Convex Hull?

I read that in a 2D space, the two points farthest away must be in the convex hull (CH). Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point ...
1
vote
0answers
34 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
2
votes
1answer
23 views

Partition overlapping polygons

On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are ...
3
votes
1answer
38 views

What is this problem? Largest set of contiguous x values for which the same y value can be held

I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is: Given a set of ...
0
votes
1answer
57 views

Determine if two edges of a graph cross? [closed]

Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great. To be ...
0
votes
0answers
41 views

Algorithm for storing polygon edges into grid

Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is? Grid has fixed dimensions and number of cells. Grid is represented by ...
3
votes
1answer
49 views

Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree

I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton ...
0
votes
1answer
37 views

Show that this algorithm does not work for determining convex polygons

Context Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no". My answer ...
0
votes
0answers
21 views
1
vote
0answers
34 views

Graham Scan - Why does the first and last points always belong to the convex hull?

Context In a 2-dimensional space, suppose $p_0$ is the origin - the lowest point of the Convex Hull (CH), and suppose $p_1, ..., p_{n-1}$ are sorted by their polar angles. When applying Graham scam, ...
1
vote
0answers
27 views

Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm. I planned to build non-self intersecting polygons ...
2
votes
1answer
43 views

How to make this recursive relationship nonrecursive? [closed]

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code. I stumbled across an important ...
2
votes
1answer
54 views

Similarity between two geometric shapes

I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it? ...
3
votes
2answers
171 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
1
vote
0answers
18 views

fraction of volume of a rectilinear grid cell within some radius of the origin [closed]

I have a sphere (radius R) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices [i,j,k] which refer to the lowest-index vertex ...
2
votes
1answer
90 views

Maximum Enclosing Convex Polygon of a Given Area

My question is very similar to another solved question. As the title indicates, the major difference in my question is that I need to find the convex polygon that encloses the maximum number of points ...
3
votes
3answers
122 views

Selecting random points at general position

How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line? The following ...
-1
votes
0answers
16 views

Closest pair of points on a line [closed]

What is the problem in “closest pair of points algorithm” if all points share the same x-coordinate or the same y-coordinate? and how the algorithm will change?
1
vote
3answers
131 views

How to find whether a point is in a line or not

Suppose in a given plain there are fixed number of lines. A point P lies on one of the line. How to find which line intersects the point P ? I am giving an example In the above graph point P is on ...
3
votes
0answers
68 views

Is finding all valid nets of a polyhedron NP-hard?

Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard? My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number ...
-1
votes
0answers
20 views

The method of recover the set of points of Voronoi diagram [closed]

If we constructed a Voronoi diagram of a set of points, and then 'lost' the set of points, can we recover the set of points from the Voronoi diagram we constructed before? What information should be ...
1
vote
1answer
36 views

Wave propagation in digital image

I believe the following question in summary is: How to approximate Euclidean distance in a digital plane? When a pebble falls on a calm surface of water a circular wave propagates. I want to color ...
2
votes
1answer
63 views

Find all neighbors at a certain distance, in 3 dimensions

I have two algorithms which I would like to implement: First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, ...
1
vote
0answers
46 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
1
vote
0answers
57 views

test points inside of polygons/piecewise-linear contours

I have a set of piecewise-linear curves (i.e. "points connected by line segments") as shown in the figure below: additional points are added on the borders (drawn in red) "closing" the open regions ...
0
votes
2answers
178 views

detect closed shapes formed by points

I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the ...
1
vote
2answers
104 views

Find the centre of a circle given two points lying on it and its radius

We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?
1
vote
0answers
52 views

Triangle mesh surface area after affine transformation

Let $\mathbb{M}$ be the set of all 3D triangle meshes. Let $a:\mathbb{M} \rightarrow \mathbb{R}$ be a function that computes surface area of the mesh. Let $\mathbb{T}$ be the set of 3D affine ...
1
vote
1answer
73 views

Number of K-sets [closed]

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
0
votes
0answers
32 views

Voronoi in 3d: line segmens and polylines (probably with qhull)

Is a 3d Voronoi diagram of line segments and polylines (determined by 2 ... n points) a "simple" extension of the diagram for points? I found qhull to be very usable for diagrams in arbitrary ...
2
votes
0answers
90 views

Any algorithm for finding Euclidean shortest path with specific constraints in 2D?

I have the following problem: In a 2D space with polygonal obstacles, find the shortest path between two given point. Without additional constraints, we can reduce it to a graph problem by ...
0
votes
0answers
73 views

How to represent circles in x-y coordinates

I would like to be able to represent circles in x-y coordinates. Each circle contains an x and y coordinates and radius in double data type. My goal is to compare circles with each other whether ...
0
votes
1answer
50 views

Partition points in a plane with a straigth line

Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned. Is there an algorithm which, when given a ratio a/b, divides the plane with a straight ...
2
votes
1answer
66 views

Finding squares touching points

I am looking for an algorithm to solve the following problem: INPUT: a set of $n$ points in the plane, $(x_1,y_1),...,(x_n,y_n)$. OUTPUT: a set of $n-1$ axis-parallel interior-disjoint squares, such ...
1
vote
2answers
330 views

Efficient algorithm for finding maximum subset of intersecting rectangles

What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such ...
0
votes
1answer
87 views

How do you find out with a DCEL if the face is to the right of a vertex?

I would like to find for any given vertex in a polygon stored in a doubly-connected edge list if the polygon is to its right or not. How do I do that without having a bunch of nested if statements? ...
4
votes
1answer
101 views

What is the minimum square partition of an almost-square rectangle?

This question is motivated by an older question about tiling an orthogonal polygon with squares. It is a generalisation of my former question about how to prove that the minimum square partition of a ...
2
votes
1answer
91 views

How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

This question is motivated by an older question about tiling an orthogonal polygon with squares.         Given a $3\times 2$ rectangle like the first image, the ...
3
votes
0answers
50 views

Help for implementing the maintenance of the connected components in the Euclidean plane in logarithmic time

I am aware of a logarithmic-time algorithm to maintain the connected components of graphs in the Euclidean plane (D. Eppstein, GF Italiano, R. Tamassia, RE Tarjan, J. Westbrook, and M. Yung. ...
1
vote
1answer
64 views

Partition points on a 2d plane with arbitrary line segment

Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P. I choose a point other than P and connect it with a line ...
1
vote
1answer
53 views

Job sites for applied/interdisciplinary mathematics related to computer science? [closed]

I'm looking for job sites in applied/interdisciplinary mathematics, more specially, say postdocs or higher positions in mathematics and medical imaging, mathematics and computer vision. I'm aware of ...
8
votes
2answers
388 views

Tiling an orthogonal polygon with squares

Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon. I found several references ...
5
votes
0answers
58 views

guillotine cuts versus general cuts

Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large boards of raw glass, of width W and ...
-1
votes
1answer
149 views

Find neighbors of node in euclidean graph

I have an euclidean graph, I want to add new node to it, and create edges between that node and all the rest of the nodes, keeping it euclidean. Now I want to sort all the nodes in the graph by ...
5
votes
1answer
80 views

Range query for sum of vectors

We have two sets of vectors of positive numbers, $X$ and $Y$ where for $x\in X$ we write $x=(x_1,x_2,\ldots,x_k)$ and similarly for $y\in Y$ we write $y=(y_1,y_2,\ldots,y_k$). We are given two ...