Skip to main content
added 87 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles. (Edit) To address MattF's point, assume $P$ is scaled to fit in a $1 \times 1$ box.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in minimum (shortest) reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a minimum/shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in minimum (shortest) reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a minimum/shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles. (Edit) To address MattF's point, assume $P$ is scaled to fit in a $1 \times 1$ box.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in minimum (shortest) reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a minimum/shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

MattF's suggestions.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Shortest Minimum reflection paths in a mirror polygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in shortestminimum (shortest) reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a shortestminimum/shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Shortest reflection paths in a mirror polygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in shortest reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Minimum reflection paths in a mirror polygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in minimum (shortest) reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a minimum/shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Link to orthogonal polygon.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in shortest reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose another purpose:

OrthogPolygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in shortest reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles, and is non-self-intersecting; also known as a rectilinear polygon. Treat every edge of $P$ as a perfect mirror, reflecting lightrays at equal angles.

Let $x$ and $y$ be points in $P$ that can be connected via a lightray path. Assume rays die at vertices, so such a path avoids vertices (except possibly at its endpoints if $x$ or $y$ is a vertex).

I am interested in shortest reflection paths between $x$ and $y$, where path length is measured by the number $k$ of reflections. For example, below the upper path from $x$ (green) to $y$ (red) reflects $k=19$ times, while the lower path reflects $k=16$ times. ($\theta$ is the start angle w.r.t. the horizontal.)

LightRaysCorridor

Here is my question:

Q. Is there an upperbound on the number of reflections in a shortest reflection path from $x$ to $y$, expressed as a function of the minimum distance between parallel edges of $P$ that can see one another vertically or horizontally?

It is known that for a given $x$, there can only be a finite number of dark points in $P$ (discussed in an earlier MO question). Assume $y$ is not one of those dark points, so that there exists a path from $x$ to $y$.

In Q I'm trying to capture the width of corridors, but perhaps the minimum distance between parallel edges is the wrong quantity.

I've simplified my question to orthogonal polygons, but my real target is simple polygons with angles rational multiples of $\pi$. Then perhaps a bound could be obtained as a function of the minimum local feature size, or some analogous measure.


Here is an orthogonal polygon, which I drew for another purpose:

OrthogPolygon

Added orthogonal polygon.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
Emphasized reflection math, partially addressing MattF's point.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
added 2 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
Removed Q2 concerning algorithm.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading