Let $P$ be a polygon. For each point $x$ on the boundary of $P$, denote by $N_P(x)$ the set of points in $P$, that are nearer to $x$ than to any other point on the boundary of $P$.

Given a subset $X$ of the boundary (e.g. an interval contained in one of the sides of $P$), what is an algorithm for computing $N_P(X)$?

Here is an example: $X$ is the blue interval at the bottom, and $N_P(X)$ is the blue polygon.

enter image description here

  • 1
    $\begingroup$ $N_P(x)$ is empty for a single point $x$ (since you can get as close as you want to $x$ from the boundary), and $N_P(X)$ wasn't defined for sets. Can you clarify what you meant by the definition of $N_P$? are the points you are talking about are some sort of input the algorithm has? $\endgroup$
    – nir shahar
    Jun 3, 2021 at 10:06
  • 2
    $\begingroup$ @nirshahar I do not think $N_P(x)$ is empty for a single point. For example, if $x$ is the leftmost blue point, then $N_P(x)$ is the perpendicular segment from $x$ to the blue point above it; the points on this segment are nearer to $x$ than to any other boundary points. $\endgroup$ Jun 3, 2021 at 11:30

1 Answer 1


The following ideas might help.

The set $X$ can be partitioned into a set of disjoint intervals such that each interval is continuous and lies on one of the sides of polygon. For each interval $I$, we can find $N_{P}(I)$ and union of all $N_{P}(I)'s$ would give the required set $N_{P}(X)$. Now, let us find $N_{P}(I)$ for an interval $I$:

  1. For ease of simplification, orient the polygon such that interval $I$ lies on the $x$-axis; similar to the one shown in your figure.
  2. Let $a$ and $b$ be the two endpoints of $I$ such that $a\leq b$. It is easy to see that the polygon region that lies within the region $y \in (-\infty,\infty)$ and $x \in (-\infty,a) \cup (b,\infty)$ does not belongs to $N_{P}(I)$.
  3. This leaves us with the region $R$ defined as $y \in (-\infty,\infty)$ and $x \in [a,b]$. Find all the segments of the polygon that lies in this region. You can do this by taking each side of the polygon and keeping its that part that lies in $R$. Suppose $S$ be this set of segments that we obtain.
  4. For every $q \in [a,b]$, we will find the region $N_{P}(q)$. Let $S_{q} \subseteq S$ be the set of segments that intersects with the line $x = q$. The segment in $S_{q}$ that is closest to the $x$-axis will be the main competitor. Let this segment be $S_{q}^{c}$ and suppose it has height $h$. If the point $(q,h/2)$ lies in the polygon, then all the points: $(q,y)$, where $y\leq|h|/2$ lies in $N_{P}(q)$; otherwise not. If we can follows this process for every $q \in [a,b]$, then the union of $N_{P}(q)$'s will give $N_{P}(I)$.

Now, how can we perform step $4$ efficiently? In other words, we need obtain the segment $S_{q}^{c}$ for every $q \in [a,b]$? It is simple. Run the sweep line algorithm on $S$ with event points being the start and end points of the segments. Keep track of the line segments that are closest to the $x$-axis. In that way, you will find $N_{P}(I)$.

  • $\begingroup$ Interesting ideas, thanks $\endgroup$ Jun 11, 2021 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.