High Dimensional Consistent DigitalSegments
Man-Kwun Chiu

Matias Korman

National Institute of Informatics

Man-Kwun Chiu

Matias Korman

Tohoku University

High Dimensional Consistent Digital Segments

Real life...

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

...is digital

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Euclidean Segments...

...Are beautiful!

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Euclidean Segments...

...Are beautiful!
Connected
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Euclidean Segments...

...Are beautiful!
Connected, uniquely defined
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Euclidean Segments...

...Are beautiful!
Connected, uniquely defined, can be extended, ...
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Digital Segments...

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Digital Segments...

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Digital Segments...

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Digital Segments...

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Consistent Digital Segments (CDS)

Digital segments satisfy 5 Axioms :S1 Grid path property
S2 Symmetry property
S3 Subsegment property
S4 Prolongation property
S5 Monotonicity property
Objective :Design digital paths for any two grid points that
preserve axioms.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Consistent Digital Segments (CDS)

Digital segments satisfy 5 Axioms :S1 Grid path property
S2 Symmetry property
S3 Subsegment property
S4 Prolongation property
S5 Monotonicity property
Objective :Design digital paths for any two grid points that
preserve axioms.
Bonus! Can they resemble Euclidean segments?

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree. (ConsistentDigital Rays (CDR))

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree. (ConsistentDigital Rays (CDR))
Intersection of two paths must be a path.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree. (ConsistentDigital Rays (CDR))
Intersection of two paths must be a path.
...also hold with all other trees.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree. (Consistent
Digital Rays (CDR))
Intersection of two paths must be a path.
...also hold with all other trees. (CDS)
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Intuitive idea

At a point we need an (infinite) tree. (ConsistentDigital Rays (CDR))
Intersection of two paths must be a path.
...also hold with all other trees. (CDS)...and that it resembles Euclidean segments!
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

How to measure resemblance?
qh(R(p, q), pq)h(pq, R(p, q))ph(A, B) = maxa∈A minb∈B dist(a, b).
The Hausdorff distance between pq and R(p, q): H(pq, R(p, q)) = max{h(pq, R(p, q)), h(R(p, q), pq)}.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

How to measure resemblance?
qh(R(p, q), pq)h(pq, R(p, q))ph(A, B) = maxa∈A minb∈B dist(a, b).
The Hausdorff distance between pq and R(p, q): H(pq, R(p, q)) = max{h(pq, R(p, q)), h(R(p, q), pq)}.
The Hausdorff distance of a CDS is defined as
maxp,q∈Zd ,||p−q||1 ≤n H(pq, R(p, q)).
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Results(d = 2) Previous work
a construction from any permutation θ of Za θ builds a quadrant

CDR(pathsfromoneppoint)

Error

any 2d orders make a CDR
Θ(log n) Hausdorff distance
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Results(d = 2) Previous work
a construction from any permutation θ of Za θ builds a quadrantCDR(d ≥ 3) New
generalize the construction
to higher dimensionsa θ builds an orthant(pathsfromoneppoint)

Error

any 2d orders make a CDR
Θ(log n) Hausdorff distance
Man-Kwun Chiu

Matias Korman

One order fixes the CDR
Θ(log n) Hausdorff distanceHigh Dimensional Consistent Digital Segments

Our Results

CDS(d = 2) Previous work
any 2d−1 orders make a CDS(pathsto/from
anywhere)Error

Θ(log n) Hausdorff distance

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Our Results

CDS(d = 2) Previous work
any 2d−1 orders make a CDS(d ≥ 3) NewSome orders work

Θ(log n) Hausdorff distanceΘ(n) Hausdorff distance(pathsto/fromanywhere)

Error

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2

q
px1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2

q
px1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .
Look at θ from p1 + p2 = 2 to q1 + q2 − 1 = 7.
θ[2, 7] = 7 ≺ 6 ≺ 4 ≺ 2 ≺ 3 ≺ 5.
Look at the position of m1 + m2 in θ[2, 7].
Red numbers represent x1 movements.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2

qpx1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .
Look at θ from p1 + p2 = 2 to q1 + q2 − 1 = 7.
θ[2, 7] = 7 ≺ 6 ≺ 4 ≺ 2 ≺ 3 ≺ 5.
Look at the position of m1 + m2 in θ[2, 7].
Red numbers represent x1 movements.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2qpx1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .
Look at θ from p1 + p2 = 2 to q1 + q2 − 1 = 7.
θ[2, 7] = 7 ≺ 6 ≺ 4 ≺ 2 ≺ 3 ≺ 5.
Look at the position of m1 + m2 in θ[2, 7].
Red numbers represent x1 movements.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2

qpx1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .
Look at θ from p1 + p2 = 2 to q1 + q2 − 1 = 7.
θ[2, 7] = 7 ≺ 6 ≺ 4 ≺ 2 ≺ 3 ≺ 5.
Look at the position of m1 + m2 in θ[2, 7].
Red numbers represent x1 movements.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Two-Dimensional Backgroundx2qpx1 + x2 = 8ox1 + x2 = 2x1

Given a permutation θ, p = (1, 1), q = (5, 3).
four moves in x1 direction and 2 moves in x2 direction.
Associate each point m = (m1 , m2 ) to integer m1 + m2 .
Look at θ from p1 + p2 = 2 to q1 + q2 − 1 = 7.
θ[2, 7] = 7 ≺ 6 ≺ 4 ≺ 2 ≺ 3 ≺ 5.
Look at the position of m1 + m2 in θ[2, 7].
Red numbers represent x1 movements.
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Let’s extend this to high dimensions!

Fix total order θ, construct a path from p to q.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Let’s extend this to high dimensions!

Fix total order θ, construct a path from p to q.
We must move |pi − qi | times in the xi -coordinate.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Let’s extend this to high dimensions!

Fix total order θ, construct a path from p to q.
We must move |pi − qi | times in the xi -coordinate.
PP
Partition θ[ i pi , i qi − 1] into d sub-intervals.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Let’s extend this to high dimensions!

Fix total order θ, construct a path from p to q.
We must move |pi − qi | times in the xi -coordinate.
PPPartition θ[ i pi , i qi − 1] into d sub-intervals.
P
mi in θ.
Look at the position ofMan-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Let’s extend this to high dimensions!

Fix total order θ, construct a path from p to q.
We must move |pi − qi | times in the xi -coordinate.
PPPartition θ[ i pi , i qi − 1] into d sub-intervals.
Pmi in θ.
Look at the position of
We need an axis-order to be consistent.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Axis-orderslope(+1, +1, +1)(+1, −1, −1)(−1, +1, +1)···
From (1, 1, 0) to (3, 5, 4)

axis-order
x1 , x2 , x3
x1 , x3 , x2
x2 , x3 , x1···
slope= (+1, +1, +1)x2x1x3

θ[2, 11] = 5 ≺ 3 ≺ 2 ≺ 7 ≺ 9 ≺ 8 ≺ 11 ≺ 10 ≺ 6 ≺ 4x2x3x1

From (1, 1, 2) to (−3, 5, 4) slope= (−1, +1, +1)

slope of p, qt = (t1 , t2 , . . . , td ) ∈ {+1, −1}d , where ti = +1 if pi ≤ qi
and is −1 if pi ≥ qi .
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRsp

In Z2 a total order determines a quadrant

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRsp

In Z2 a total order determines a quadrant
Any 4 total orders combined form a CDR

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

Fix p ∈ Z d , total order θ, and slope t, create an orthant
Denoted by TOC (θ, p, t).

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

Fix p ∈ Z d , total order θ, and slope t, create an orthant
Denoted by TOC (θ, p, t).
S⇒ Glue 2d orthants t∈T TOC (θt , p, t) of different slopes
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

Fix p ∈ Z d , total order θ, and slope t, create an orthant
Denoted by TOC (θ, p, t).
S⇒ Glue 2d orthants t∈T TOC (θt , p, t) of different slopes
Question do we always make a CDR?
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

TheoremSt∈T TOC (θt , p, t) is a CDR if and only if
θt = θt0 − t0 · p + t · p.

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

Theorem
St∈T TOC (θt , p, t) is a CDR if and only if
θt = θt0 − t0 · p + t · p.
Examplep = (2, 2, 0), t = (+1, +1, +1), t0 = (+1, −1, −1)
t · p = 4, t0 · p = 0, −t0 · p + t · p = 4

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDRs

Theorem
St∈T TOC (θt , p, t) is a CDR if and only if
θt = θt0 − t0 · p + t · p.
Examplep = (2, 2, 0), t = (+1, +1, +1), t0 = (+1, −1, −1)
t · p = 4, t0 · p = 0, −t0 · p + t · p = 4

θt0
θt = θt0 +4==

Man-Kwun Chiu... ≺ 5 ≺ 4 ≺ 6 ≺ ...
. . . ≺ 9 ≺ 8 ≺ 10 ≺ . . .

Matias Korman

High Dimensional Consistent Digital Segments

What about CDSs?

p1

Look at CDS now (paths for any pair of points)

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

What about CDSs?

p1

Look at CDS now (paths for any pair of points)
In Z 2 , two orders create a half CDR

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

What about CDSs?

p1
p2 p3

Look at CDS now (paths for any pair of points)
In Z 2 , two orders create a half CDR
Repeat at all points to get a CDS

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

What about CDSs?

p1
p2 p3

Look at CDS now (paths for any pair of points)
In Z 2 , two orders create a half CDRRepeat at all points to get a CDS

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

What about CDSs?

p1
p2 p3

Look at CDS now (paths for any pair of points)
In Z 2 , two orders create a half CDR
Repeat at all points to get a CDS
Similar approach for higher dimensions?
Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDSs
One total order θ fixes a CDR TOC (θ, p)

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDSs
One total order θ fixes a CDR TOC (θ, p)
S
To make a CDS, we consider p∈Zd TOC (θ, p).
TheoremSp∈Zd TOC (θ, p) is CDS if and only if θ = θ + 2 andθ = −(θ + 1)−1 .

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDSs
One total order θ fixes a CDR TOC (θ, p)
S
To make a CDS, we consider p∈Zd TOC (θ, p).
TheoremSp∈Zd TOC (θ, p) is CDS if and only if θ = θ + 2 andθ = −(θ + 1)−1 .
ExampleAssume that 1 ≺θ 2 in θMan-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDSs
One total order θ fixes a CDR TOC (θ, p)
S
To make a CDS, we consider p∈Zd TOC (θ, p).
TheoremSp∈Zd TOC (θ, p) is CDS if and only if θ = θ + 2 andθ = −(θ + 1)−1 .
ExampleAssume that 1 ≺θ 2 in θ
θ =θ+2Man-Kwun Chiu

⇒ 3 ≺θ 4 must holdMatias Korman

High Dimensional Consistent Digital Segments

Necessary and sufficient condition for CDSs
One total order θ fixes a CDR TOC (θ, p)
S
To make a CDS, we consider p∈Zd TOC (θ, p).
TheoremSp∈Zd TOC (θ, p) is CDS if and only if θ = θ + 2 andθ = −(θ + 1)−1 .
ExampleAssume that 1 ≺θ 2 in θ

⇒ 3 ≺θ 4 must hold−1
θ = −(θ + 1) ⇒ −3 ≺θ −2 must hold
θ =θ+2

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)

qp
For any p, q we must have R(p, q) = R(q, p).

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)

qp
For any p, q we must have R(p, q) = R(q, p).
R(p, q) is constructed with θt , R(q, p) with θ−t

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)q

R(q, p)p
For any p, q we must have R(p, q) = R(q, p).
R(p, q) is constructed with θt , R(q, p) with θ−tPaths must be identical

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)q

R(q, p)(a1 , a2 )a1 + a2 in θt(a1 + 1, a2 )−(a1 + a2 + 1) in θ−tp
For any p, q we must have R(p, q) = R(q, p).
R(p, q) is constructed with θt , R(q, p) with θ−tPaths must be identical

Decisions are at different end points

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)

qR(q, p)(a1 , a2 )a1 + a2 in θt(a1 + 1, a2 )−(a1 + a2 + 1) in θ−tp
For any p, q we must have R(p, q) = R(q, p).
R(p, q) is constructed with θt , R(q, p) with θ−tPaths must be identical

Decisions are at different end points
θ−t ≈ −(θt + 1)

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Why θ = −(θ + 1)−1 ?
R(p,q)

qR(q, p)(a1 , a2 )a1 + a2 in θt(a1 + 1, a2 )−(a1 + a2 + 1) in θ−tp
For any p, q we must have R(p, q) = R(q, p).
R(p, q) is constructed with θt , R(q, p) with θ−tPaths must be identicalDecisions are at different end points
θ−t ≈ −(θt + 1)

The axis-order of −t is the reverse axis-order of t

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

SummaryResults
Extended the approach of Christ et al to Zd .
We can always make a CDR from θ.
Characterize when we make a CDS.
Always high Hausdorff distance

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Summary
Results
Extended the approach of Christ et al to Zd .
We can always make a CDR from θ.
Characterize when we make a CDS.
Always high Hausdorff distanceLet’s not use total orders in high dimensions!

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Summary
Results
Extended the approach of Christ et al to Zd .
We can always make a CDR from θ.
Characterize when we make a CDS.
Always high Hausdorff distanceLet’s not use total orders in high dimensions!
Open Problems
Different approach to make CDSs?
o(n) Hausdorff distance?
Fully characterize CDRs/CDSs in Zd ?

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments

Questions?Comments?

Thank you!

Man-Kwun Chiu

Matias Korman

High Dimensional Consistent Digital Segments