Tagged Questions

Questions algorithmic solutions of geometric problems.

17 views

Generating a random, dense set of points subject to proximity restrictions?

I recently read a paper about hyperuniform distributions, which mentioned that one way to generate a rectangle filled with hyperuniformly-distributed points is the following: Choose a uniformly-...
20 views

Percent of rectangle intersected by circle

I'm searching for an algorithm which, given specifications of a circle and a rectangle, returns the percentage of the rectangle intersected by the circle. In other words, given $(x,y)$ (the center of ...
52 views

Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
47 views

Finding a minimal width strip which encloses a set of points in the plane

Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points? Definitions: A strip is defined by two parallel lines and the ...
79 views

Generate random point inside a polyhedron

I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)? ...
17 views

k-Closest pairs in Delaunay triangulation

Assume there is a set of points $S$ in $\mathbb{R^2}$. In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors. I ...
44 views

Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)

There is a finite set of points $S$ in the plane with $|S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the ...
30 views

Hyperplane through origin which goes through most number of points

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects ...
34 views

Algorithm to enclose a 2D-gridbased-room efficient

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort. Here a little Example: In this example black squares are not ...
21 views

Identify large (convex) polygons

I have a point cloud that has several connections. What I want to identify are the largest (by area) irregular (convex) polygons. I put convex in brackets as it is not fully necessary (like in the red ...
50 views

Number of N Shaped figures formed from the set of points

Given k points on 2d plane and i need to find the number of N shaped figures from these k points. lets consider four different points from the set and name them A,B ,C ,and D (in that order). These ...
56 views

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Let's say you have pixel bitmaps that look something like this: From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the ...
76 views

Repeated point in polygon: preprocessing complexity given logarithmic query time?

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is ...
31 views

Snap/Fit a chain of lines to points

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it. Here is ...
32 views

Red-blue intersection requirements

In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean ...
59 views

Find internal surfaces in an oriented mesh

I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
69 views

smallest circle that covers two points with its center in x axis

I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know ...
64 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
100 views

Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$. My first guess was ...
34 views

Computing the right tangent of two convex hulls

My question deals with the algorithm of computing the convex hull in 2D by Preparata. Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex ...
33 views

Voronoi Diagram Question

I am stuck on that question, it's about Voronoi diagrams Show that for some set of $n$ points, there can be $\Omega(n^2)$ intersections between the edges of the Voronoi diagram and the edges of ...
28 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
103 views

79 views

Find cell neighbors of a given edge in a 2D grid [closed]

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, ...
19 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
37 views

73 views

How to find the original coordinates of a point inside an irregular rectangle?

I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms. I'll try to explain my problem as much as I can. ...
92 views

How to handle horizontal lines in the Polyfill Algorithm?

When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled? For ...
66 views

Voronoi cells for rectangles

I am looking for a reference on the following variant of a Voronoi diagram: Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint. Instead of Euclidean ...
77 views

Bentley–Ottmann algorithm time complexity issue

In the Bentley–Ottmann algorithm, Regarding : Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the ...
608 views

Finding a way out of a polygon

There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$: The goal is to select one of the polygons, say $D_i$, and attach to ...
99 views

Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
24 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \... 0answers 247 views Moving a set of points in the plane subject to constraints I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum. Let$X$denote the disjoint union of$n$one-point sets. Let$f:X\...
I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned ...