3D ealiza ion o wo iangula ions o a on ex p olygon.
Se gey Be eg
a
,
a
Depa men o Compu e Siene, Uni e si y o Texas a Dal las, Box 830688, Riha dson, TX 75083, USA.
Abs a
We s udy he p oblem o ons u ion o a on ex 3-p oly op e whose (i) shadow b ounda y has
n
e ies and (ii)
wo hulls, upp e and lowe , a e isomo phi o wo gi en iangula ion s o a on ex
n
-gon. Ba ne e [1℄ p o ed he
exis ene o a on ex 3-p oly op e in gene al ase. We show ha , in ou ase, a p oly op e an b e ons u ed using
an op e a ion o edge  ea ion.
Key wo ds:
iangula ion, on ex p oly op e, S eini z heo em
1. In o du ion
Le
P
b e a on ex p olygon in he
xy
-plane wi h
n
e ies. Two iangula ions o
P
a e alled
dis-
in
i he only edges hey sha e a e he edges o
P
. Le
T
1
and
T
2
b e wo dis in iangula ions o
P
. A he
Fi s Canadian Con e ene on Compu-
a ional Geome y
Leo Guibas onje u ed ha i
is always p ossible o p e u b he e ies o
P
e -
ially ou (i.e., by displaemen s pa allel o he
z
-axis) so ha he p olygon
P
b eomes a spa ial
p olygon
P
0
suh ha he on ex hull o
P
0
is a
on ex p olyhed on onsis ing o wo iangula ed
ups glued along
P
0
,
and
he iangula ion o he
upp e up (i.e., hose aes o ien ed owa d +
z
) is
ha sp eied as
T
1
, and he iangula ion o he
lowe up is ha sp eied as
T
2
[4℄.
Bo is Beks e [2℄ disp o ed Guibas' onje u e
by showing a oun e example, a on ex hexagon
wi h wo iangula ions. Ma lin and Toussain [3℄
onside ed he ompu a ional p oblem o deiding
whe he a iple (
P ; T
1
; T
2
) admi s a ealiza ion in
R
3
. They edued he p oblem o a linea p og am-
ming p oblem wi h
O
(
n
2
) inequali y ons ain s
and
n
a iables. The a iables a e
z
-o o dina es o
li ed e ies o
P
and he ons ain s o ep ond
o e ex- ae ela ions: he e ies mus b e b e-
low/ab o e he planes passing h ough aes o he
Email add ess:
bespu dallas.edu
(Se gey Be eg).
URL:
h p://u dallas.edu/~sxb027100
(Se gey
Be eg).
upp e /lowe up o
P
0
. The numb e o ons ain s
an b e d opp ed o 2
n

6 =
j
T
1
j
+
j
T
2
j
by onside -
ing dihed al angles o esp onding o diagonals o
he iangula ions [7℄.
Guibas onje u e is ela ed o S eini z's heo-
em [5℄.
S eini z's Theo em:
A g aph
G
is isomo phi
o he edge g aph o a on ex 3-poly ope i and
only i
G
is 3-onne ed and plana .
By S eini z's heo em he g aph (
P ; T
1
[
T
2
) is he
edge g aph o a on ex 3-p oly op e [3℄. Ao ding
o Ba ne e's heo em [1℄, e e y 3-p oly op e wi h a
Hamil onian i ui has ealiza ion suh ha he
Hamil onian i ui is a shadow b ounda y. This
implies ha Guibas' onje u e is ue up o a om-
bina o ial de o ma ion [2℄. Fo mally his an b e
s a ed as ollows.
Theo em 1
Fo any wo dis in iangula ions
T
1
and
T
2
o a on ex polygon
P
2
in
R
2
wi h
n
e ies, he e is a on ex poly ope
P
3
in
R
3
wi h
n
e ies suh ha
(i)
he
xy
-shadow
S
o
P
3
on ains
al l i s e ies, and
(ii)
he e is a isomo phism

:
P
2
!
S
ha maps he edges o
T
1
( esp.
T
2
) o he
edges o he uppe hul l o
P
3
( esp. he lowe hul l).
Ba ne e's p o o deals wi h gene al aes (no
jus iangles) due o i s gene ali y. In his pap e
we gi e a die en p o o o Theo em 1 ha uses
only iangula aes o p oly op es whih an b e
u ned in o a mo e obus algo i hm o nding a
ombina o ial ealiza ion o (
P ; T
1
; T
3
) in
R
3
.
Realiza ion ques ions ha e b een s udied in om-
20 h EWCG Se ille, Spain (2004)
20 h Eu op ean Wo kshop on Compu a ional Geome y
pu e g aphis and sene analysis as well. Sugiha a
[6℄ es ablished neessa y and suÆien ondi ions
whe he a line d awing in he plane an b e ealized
in
R
3
by li ing.
We all a iple (
P ; T
1
; T
2
) a
ongu a ion
. We
all a map

sa is ying he ondi ions o Theo em
1 a
ealiza ion
.
2. Edge on a ion
(a)
(b)
p1
p2
p3
p1
p2
p3
Fig. 1. (a) Edge on a ion o a iangula ion. (b) Edge
on a ion o wo iangula ions. The diagonals o one i-
angula ion a e solid and he diagonals o he o he ian-
gula ion a e dashed.
As in Ba ne e's p o o we use he op e a ion o
edge emo al. The die ene is ha we will no
apply i o diagonals o
P
. This p e en s he ap-
p ea ene o aes wi h mo e han h ee e ies.
The
edge on a ion
in a ongu a ion is dened
by ide i ying he edge enp oin s. I applied o one
iangula ion o
P
, i p o dues a iangula ion, see
Fig. 1 (a) o example whe e he edge
p
1
p
2
is on-
a ed. When applied o wo iangula ions, we
wan he edued iangula ions o b e dis in . An
edge
e
o a ongu a ion (
P ; T
1
; T
2
) is
on a ible
i he new iangula ions
T
0
1
and
T
00
2
a e dis in .
In gene al, no all edges a e on a ible. Fo ex-
ample, he edge
p
1
p
2
in he Fig. 2 (a) is no on-
a ible sine wo edges
p
1
p
6
and
p
2
p
6
om die -
en iangula ions oinide a e he on a ion o
p
1
p
2
.
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p1=p4
p2
p3
(a)
(b)
Fig. 2. (a) The edge (
p
1
; p
2
) is no on a ible. (b) The
edge on a ion o
n
= 4.
Lemma 2
Le
C
be a ongu a ion wi h
n

4
e ies. The e is a on a ible edge o
C
among
he edges o he on ex polygon.
PROOF.
I
n
= 4 hen e e y edge o he on ex
p olygon is on a ible, see Fig. 2 (b). We p o e
he lemma o
n

5. Supp ose o he on a y ha
he e is a ongu a ion (
P ; T
1
; T
2
) suh ha all
edges o
P
a e no on a ible. Le
p
1
;:::;p
n
b e
Ma h 25-26, 2004 Se ille (Spain)
he e ies o
P
in lo kwise o de . The edge
p
1
p
2
is no on a ible. Then he e is a e ex
p
k
;
4

k

n

1 suh ha
p
1
p
k
is an edge o one iangu-
la ion, say
T
1
, and
p
2
p
k
is an edge o
T
2
, see Fig. 3
(a).
Conside an edge
p
i
p
i
+1
;
2

i

k

1. Sine
p
i
p
i
+1
is no on a ible, he e is a e ex
p

(
i
)
suh ha
p
i
p

(
i
)
is a diagonal o
T
j
; j
= 1
;
2 and
p
i
+1
p

(
i
)
is a diagonal o
T
3

j
, see Fig. 3 (a). We
all
p

(
i
)
a
wi ness
sine i india es ha
p
i
p
i
+1
is
no on a ible. A leas one e ex o
p
i
; p
i
+1
g
,
say
p
l
, is die en om
p
2
and
p
k
. Then he edge
p
l
p

(
i
)
do es no  oss one o he edges
p
1
p
k
o
p
2
p
k
.
The e o e

(
i
) is an index in he ange 1
;:::;k
.
p1
p2
pk
P
pi
pi+1
pc(i)
pi
pi+1 pi+2
pc(i+1) pc(i)
p1pk
(a)
(b)
e1
e2
Fig. 3. Lemma 2.
We all
p

(
i
)
a
le wi ness
i

(
i
)
< i
. We all
p

(
i
)
a
igh wi ness
i

(
i
)
> i
+ 1. Eah wi ness is ei he
le o igh sine

(
i
)
6
=
i; i
+ 1. No e ha
p

(2)
is
a igh wi ness and
p

(
k

1)
is a le wi ness. Thus
he e is an index
i;
2

i

k

2 suh ha
p

(
i
)
is
he igh index and
p

(
i
+1)
is he le index, see Fig.
3 (b). Then
p
i
p

(
i
)
, a diagonal o a iangula ion
T
j
,
in e se s b o h diagonals
e
1
= (
p
i
+1
; p

(
i
+1)
) and
e
2
= (
p
i
+2
; p

(
i
+1)
). Ei he
e
1
o
e
2
is a diagonal o
T
j
. Con adi ion.
3. Edge  ea ion
We dene an op e a ion o
edge  ea ion
as he
e e se op e a ion o he edge on a ion. The ol-
lowing lemma h a e izes he hange o he on-
gu a ion when an edge is  ea ed. We deno e he
sequene o indies om
i
o
j
in lo kwise o de
by
i; i
+ 1
;:::;j
g
.
Lemma 3 (Edge  ea ion)
Le
C
= (
P ; T
1
; T
2
)
be a ongu a ion wi h
n

3
e ies whe e
P
=
p
1
;:::;p
n
g
. Suppose ha an edge
e
= (
q
1
; q
2
)
is  ea ed in plae o a e ex
p
i
2
P
. Le
C
0
=
(
P
0
; T
0
1
; T
0
2
)
be he ongu a ion ob ained by epla-
ing a e ex
p
i
by an edge
e
= (
q
1
; q
2
)
in lokwise
o de . Then he e a e wo edges
(
p
i
; p
j
)
2
T
1
and
(
p
i
; p
k
)
2
T
2
suh ha
{ an edge
(
p
l
; p
i
)
2
T
1
; l
2
i
+ 1
; i
+ 2
;:::;j
g
is
eplaed by he edge
(
p
l
; q
1
)
2
T
0
1
, and
{ an edge
(
p
l
; p
i
)
2
T
1
; l
2
j; j
+ 1
;:::;i

1
g
is
eplaed by he edge
(
p
l
; q
2
)
2
T
0
1
, and
{ an edge
(
p
l
; p
i
)
2
T
2
; l
2
i
+ 1
; i
+ 2
;:::;p
k
g
is
eplaed by he edge
(
p
l
; q
1
)
2
T
0
2
, and
{ an edge
(
p
l
; p
i
)
2
T
2
; l
2
k ; k
+ 1
;:::;i

1
g
is
eplaed by he edge
(
p
l
; q
2
)
2
T
0
2
.
We show ha an edge an b e always  ea ed.
Theo em 4
Le
C
= (
P ; T
1
; T
2
)
be a ongu a ion
wi h
n

3
e ies and le

:
P
!
R
3
be i s e-
aliza ion in
R
3
. Le
C
0
= (
P
0
; T
0
1
; T
0
2
)
be he on-
gu a ion ob ained by an edge  ea ion. The e is a
ealiza ion o
C
0
i he e is a ealiza ion o
C
.
Theo em 1 ollows om Theo em 4.
Re e enes
[1℄ D. W. Ba ne e. P o je ions o 3-p oly op es.
Is ael J.
Ma h.
, 8:304{308, 1970.
[2℄ B. V. Deks e . Con ex hulls o spa ial p olygons wi h
a xed on ex p o je ion.
Bei age zu Algeb a und
Geome ie/Con ibu ions o Algeb a and Geome y
,
36:123{124, 1995.
[3℄ B. Ma lin and G. Toussain . Cons u ing on ex 3-
p oly op es om wo iangula ions o a p olygon. In
P o.
20 h Eu op ean Wo kshop on Compu a ional Geome y
pi−1
pi
pi+1
pjpk
pi−1
q1
pi+1
pjpk
q2e
Fig. 4. Edge  ea ion.
14 h Canad. Con . Compu . Geom.
, pp. 36{39, 2002,
h p://www.g.a/p oeedings/2002/28.ps
.
[4℄ W. J. Mose . P oblems, p oblems, p oblems.
Dis e e
Applied Ma hema is
, 31:201{225, 1991.
[5℄ E. S eini z and H. Rademahe .
Vo lesungen ube die
Theo ie de Polyede
. Julius Sp inge , Be lin, Ge many,
1934.
[6℄ K. Sugiha a. A neessa y and suÆien ondi ion o a
pi u e o ep esen a p olyhed al sene.
IEEE T ans.
on Pa e n Analysis and Mah. In el ligene
, 6(5):578{
586, 1984.
[7℄ G. Toussain . Pe sonal ommunia ion.