@STRING{colt93 = "Proceedings of the Sixth Annual ACM Conference on
Computational Learning Theory" }
@STRING{jacm = "Journal of the Association for Computing Machinery" }
@STRING{jma = "Journal of Multivariate Analysis" }
@STRING{lncs = "Lecture Notes of Computer Science, Springer" }
@STRING{lncs = "Lecture Notes in Computer Science" }
@STRING{nips = "Advances in Neural Information Processing Systems" }
@STRING{pecs = "Colloquia Mathematica Societatis Janos Bolai, 57.\ Limit
Theorem in Probability and Statistics, Pecs (Hungary)" }
@STRING{spl = "Statistics \& Probability Letters" }
@InProceedings{aabekm-nesca-00,
author = {O. Aichholzer and F. Aurenhammer and B. Brandtst\"atter
and T. Ebner and H. Krasser and C. Magele},
title = {Niching evolution strategy with cluster algorithms},
booktitle = {$9^{th}$ Biennial IEEE Conf. Electromagnetic Field
Computations},
year = 2000,
address = {Milwaukee, Wisconsin, USA},
abstract = {In most real world optimization problems one tries to
determine the global among some or even numerous local
solutions within the feasible region of parameters. On the
other hand, it could be worth to investigate some of the
local solutions as well. Therefore, a most desirable
behaviour would be, if the optimization strategy behaves
globally and yields additional information about local
minima detected on the way to the global solution. In this
paper a clustering algorithm has been implemented into an
Higher Order Evolution Strategy in order to achieve these
goals.}
}
@Article{aabk-ptsnt-03,
author = {O. Aichholzer and F. Aurenhammer and P. Brass and H.
Krasser},
title = {Pseudo-Triangulations from Surfaces and a Novel Type of
Edge Flip},
journal = {SIAM Journal on Computing},
volume = {32},
year = {2003},
pages = {1621--1653},
abstract = {We prove that planar pseudo-triangulations have
realizations as polyhedral surfaces in three-space. Two
main implications are presented: The spatial embedding
leads to a novel flip operation that allows for a drastical
reduction of flip distances, especially between (full)
triangulations. Moreover, several key results for
triangulations, like flipping to optimality, (constrained)
Delaunayhood, and a convex polytope representation, are
extended to pseudo-triangulations in a natural way.},
address = {Graz, Austria}
}
@InProceedings{aabk-sept-03,
author = {O. Aichholzer and F. Aurenhammer and P. Brass and H.
Krasser},
title = {Spatial Embedding of Pseudo-Triangulations},
booktitle = {Proc. $19^{th}$ Ann. ACM Symp. Computational Geometry},
address = {San Diego, California, USA},
volume = 19,
pages = {144--153},
year = 2003,
abstract = {We show that pseudo-triangulations have natural embeddings
in three-space. As a consequence, various concepts for
triangulations, like flipping to optimality, (constrained)
Delaunayhood, and a polytope representation carry over to
pseudo-triangulations.}
}
@InProceedings{aabkmmr-eshc-01,
author = {O. Aichholzer and F. Aurenhammer and B. Brandtst\"atter
and H. Krasser and C. Magele and M. M\"uhlmann and W.
Renhart},
title = {Evolution trategy and ierarchical lustering},
booktitle = {$13^{th}$ COMPUMAG Conference on the Computation of
Electromagnetic Fields},
year = 2001,
address = {Lyon-Evian, France},
abstract = {Multi-objective optimization problems, in general, exhibit
several local optima besides a global one. A desirable
feature of any optimization strategy would therefore be to
supply the user with as many information as possible about
local optima on the way to the global solution. In this
paper a hierarchical clustering algorithm implemented into
a higher order Evolution Strategy is applied to achieve
these goals.}
}
@Article{aaghhhkrv-mefpp-07,
author = {O. Aichholzer and F. Aurenhammer and P. Gonzalez-Nava and
T. Hackl and C. Huemer and F. Hurtado and H. Krasser and S.
Ray and B. Vogtenhuber},
title = {Matching edges and faces in polygonal partitions},
journal = {Computational Geometry: Theory and Applications},
year = {2008},
volume = 39,
pages = {134--141},
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank-$k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence,
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.}
}
@InProceedings{aaghhhkrv-mefpp-05,
author = {O. Aichholzer and F. Aurenhammer and P. Gonzalez-Nava and
T. Hackl and C. Huemer and F. Hurtado and H. Krasser and S.
Ray and B. Vogtenhuber},
title = {Matching edges and faces in polygonal partitions},
booktitle = {Proc. $17^{th}$ Canadian Conference on Computational
Geometry CCCG '05},
pages = {123--126},
year = 2005,
address = {Windsor, Ontario},
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank-$k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence,
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.}
}
@InProceedings{aahk-tct-01,
author = {O. Aichholzer and F. Aurenhammer and F. Hurtado and H.
Krasser},
title = {Towards Compatible Triangulations},
booktitle = {Proc. $7^{th}$ Ann. Int'l. Computing and Combinatorics
Conf. COCOON'01, Lecture Notes in Computer Science},
pages = {101--110},
year = 2001,
volume = {2108},
address = {Guilin, China},
editor = {Jie Wang},
publisher = {Springer Verlag},
abstract = {We state the following conjecture: any two planar
$n$-point sets (that agree on the number of convex hull
points) can be triangulated in a compatible manner, i.e.,
such that the resulting two planar graphs are isomorphic.
The conjecture is proved true for point sets with at most
three interior points. We further exhibit a class of point
sets which can be triangulated compatibly with any other
set (that satisfies the obvious size and hull
restrictions). Finally, we prove that adding a small number
of Steiner points (the number of interior points minus two)
always allows for compatible triangulations.}
}
@Article{aahk-tct-01b,
author = {O. Aichholzer and F. Aurenhammer and F. Hurtado and H.
Krasser},
title = {Towards Compatible Triangulations},
year = 2003,
journal = {Theoretical Computer Science},
note = {Special Issue},
volume = {296},
pages = {3--13},
publisher = {Elsevier},
abstract = {We state the following conjecture: any two planar
$n$-point sets (that agree on the number of convex hull
points) can be triangulated in a compatible manner, i.e.,
such that the resulting two triangulations are
topologically equivalent. The conjecture is proved true for
point sets with at most three interior points. We further
exhibit a class of point sets which can be triangulated
compatibly with any other set that satisfies the obvious
size and hull restrictions. Finally, we prove that adding a
small number of extraneous points (the number of interior
points minus two) always allows for compatible
triangulations.}
}
@InProceedings{aahk-tspt-05,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and H.
Krasser},
title = {Transforming spanning trees and pseudo-triangulations},
booktitle = {Proc. $21^{st}$ European Workshop on Computational
Geometry EuroCG '05},
pages = {81--84},
year = 2005,
address = {Eindhoven, The Netherlands},
abstract = {Let $T_{S}$ be the set of all crossing-free straight line
spanning trees of a planar $n$-point set~$S$. Consider the
graph ${\cal T}_S$ where two members $T$ and $T'$ of
$T_{S}$ are adjacent if $T$ intersects $T'$ only in points
of~$S$ or in common edges. We prove that the diameter
of~${\cal T}_S$ is $O(\log k)$, where $k$ denotes the
number of convex layers of $S$. Based on this result, we
show that the flip graph~${\cal P}_S$ of
pseudo-triangulations of~$S$ (where two
pseudo-triangulations are adjacent if they differ in
exactly one edge -- either by replacement or by removal)
has a dia\-meter of $O(n \log k)$. This sharpens a known
$O(n \log n)$ bound. Let~${\cal \widehat{P}}_S$ be the
induced subgraph of pointed pseudo-triangulations of~${\cal
P}_S$. We present an example showing that the distance
between two nodes in~${\cal \widehat{P}}_S$ is strictly
larger than the distance between the corresponding nodes
in~${\cal P}_S$.}
}
@Article{aahk-tspt-06,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and H.
Krasser},
title = {Transforming spanning trees and pseudo-triangulations},
journal = {Information Processing Letters},
pages = {19--22},
volume = {97},
year = 2006,
abstract = {Let $T_{S}$ be the set of all crossing-free straight line
spanning trees of a planar $n$-point set~$S$. Consider the
graph ${\cal T}_S$ where two members $T$ and $T'$ of
$T_{S}$ are adjacent if $T$ intersects $T'$ only in points
of~$S$ or in common edges. We prove that the diameter
of~${\cal T}_S$ is $O(\log k)$, where $k$ denotes the
number of convex layers of $S$. Based on this result, we
show that the flip graph~${\cal P}_S$ of
pseudo-triangulations of~$S$ (where two
pseudo-triangulations are adjacent if they differ in
exactly one edge -- either by replacement or by removal)
has a dia\-meter of $O(n \log k)$. This sharpens a known
$O(n \log n)$ bound. Let~${\cal \widehat{P}}_S$ be the
induced subgraph of pointed pseudo-triangulations of~${\cal
P}_S$. We present an example showing that the distance
between two nodes in~${\cal \widehat{P}}_S$ is strictly
larger than the distance between the corresponding nodes
in~${\cal P}_S$.}
}
@InProceedings{aak-aptnl-03,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {Adapting (Pseudo)-Triangulations with a Near-Linear Number
of Edge Flips},
booktitle = {Lecture Notes in Computer Science 2748, Proc. 8th
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {2748},
pages = {12--24},
year = 2003,
abstract = {We provide two results on flip distances in
pseudo-triangulations -- for minimum pseudo-triangulations
when using traditional flips operations, as well as for
triangulations when a novel and natural edge flip operation
is included into the repertoire of admissible flips. The
obtained flip distance lengths are $O(n \log^2 n)$ and $O(n
\log n)$, respectively. Our results partially rely on new
partitioning results for pseudo-triangulations which may be
of separate interest.}
}
@InProceedings{aak-cncg-02,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {On the Crossing Number of Complete Graphs},
year = 2002,
booktitle = {Proc. $18^{th}$ Ann. ACM Symp. Computational Geometry},
pages = {19--24},
address = {Barcelona, Spain},
htmlnote = {See also our crossing
number homepage.},
abstract = {Let $\overline{cr}(G)$ denote the rectilinear crossing
number of a graph $G$. We determine
$\overline{cr}(K_{11})=102$ and
$\overline{cr}(K_{12})=153$. Despite the remarkable hunt
for crossing numbers of the complete graph~$K_n$ --
initiated by R.~Guy in the 1960s -- these quantities have
been unknown for $n>10$ to~date. Our solution mainly relies
on a tailor-made method for enumerating all inequivalent
sets of points (so-called order types) of size $11$. Based
on these findings, we establish new upper and lower bounds
on $\overline{cr}(K_{n})$ for general~$n$. Specific values
for $n \leq 45$ are given, along with significantly
improved asymptotic values. The asymptotic lower bound is
immediate from the fact $\overline{cr}(K_{11})=102$,
whereas the upper bound stems from a novel construction of
drawings with few crossings. The construction is shown to
be optimal within its frame. The tantalizing question of
determining $\overline{cr}(K_{13})$ is left open. The
latest ra(n)ge is $\{221,223,225,227,229\}$; our conjecture
is $\overline{cr}(K_{13}) = 229$.}
}
@InProceedings{aak-cncg-02b,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {On the Crossing Number of Complete Graphs - Extended
Abstract},
year = 2002,
booktitle = {Proc. $18^{th}$ European Workshop on Computationl Geometry
CG '02 Warszawa},
pages = {90-92},
address = {Warszawa, Poland},
htmlnote = {See also our crossing
number homepage.},
abstract = {Let $\overline{cr}(G)$ denote the rectilinear crossing
number of a graph $G$. We determine
$\overline{cr}(K_{11})=102$ and
$\overline{cr}(K_{12})=153$. Despite the remarkable hunt
for crossing numbers of the complete graph~$K_n$ --
initiated by R.~Guy in the 1960s -- these quantities have
been unknown for $n>10$ to~date. Our solution mainly relies
on a tailor-made method for enumerating all inequivalent
sets of points (so-called order types) of size $11$. Based
on these findings, we establish new upper and lower bounds
on $\overline{cr}(K_{n})$ for general~$n$. Specific values
for $n \leq 45$ are given, along with significantly
improved asymptotic values. The asymptotic lower bound is
immediate from the fact $\overline{cr}(K_{11})=102$,
whereas the upper bound stems from a novel construction of
drawings with few crossings. The construction is shown to
be optimal within its frame. The tantalizing question of
determining $\overline{cr}(K_{13})$ is left open. The
latest ra(n)ge is $\{221,223,225,227,229\}$; our conjecture
is $\overline{cr}(K_{13}) = 229$.}
}
@Article{aak-cncg-06,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {On the Crossing Number of Complete Graphs},
year = 2006,
journal = {Computing},
pages = {165--176},
volume = {76},
htmlnote = {See also our crossing
number homepage.},
abstract = {Let $\overline{cr}(G)$ denote the rectilinear crossing
number of a graph~$G$. We determine
$\overline{cr}(K_{11})=102$ and
$\overline{cr}(K_{12})=153$. Despite the remarkable hunt
for crossing numbers of the complete graph~$K_n$ --
initiated by R.~Guy in the 1960s -- these quantities have
been unknown for \mbox{$n>10$} to~date. Our solution mainly
relies on a tailor-made method for enumerating all
inequivalent sets of points (order types) of size~$11$.
Based on these findings, we establish a new upper bound on
$\overline{cr}(K_{n})$ for general~$n$. The bound stems
from a novel construction of drawings of $K_{n}$ with few
crossings.}
}
@InProceedings{aak-ctps-01,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {On Compatible Triangulations of Point Sets},
booktitle = {Proc. $17^{th}$ European Workshop on Computational
Geometry CG '2001},
pages = {23--26},
year = 2001,
address = {Berlin, Germany},
abstract = {Two conjectures on compatible triangulations for planar
point sets are stated and proven for small sets and for
special sets of arbitrary size.}
}
@InProceedings{aak-eotsp-01,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {Enumerating Order Types for Small Point Sets with
Applications},
booktitle = {Proc. $17^{th}$ Ann. ACM Symp. Computational Geometry},
pages = {11--18},
year = 2001,
address = {Medford, Massachusetts, USA},
htmlnote = {See also our order
type homepage.},
abstract = {Order types are a means to characterize the combinatorial
properties of a finite point configuration. In particular,
the crossing properties of all straight-line segments
spanned by a planar $n$-point set are reflected by its
order type. We establish a complete and reliable data base
for all possible order types of size $n=10$ or less. The
data base includes a realizing point set for each order
type in small integer grid representation. To our
knowledge, no such project has been carried out before. We
substantiate the usefulness of our data base by applying it
to several problems in computational and combinatorial
geometry. Problems concerning triangulations, simple
polygonalizations, complete geometric graphs, and $k$-sets
are addressed. This list of possible applications is not
meant to be exhaustive. We believe our data base to be of
value to many researchers who wish to examine their
conjectures on small point configurations. }
}
@Article{aak-eotsp-01a,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {Enumerating Order Types for Small Point Sets with
Applications},
journal = {Order},
pages = {265--281},
volume = 19,
year = {2002},
htmlnote = {See also our order
type homepage.},
abstract = {Order types are a means to characterize the combinatorial
properties of a finite point configuration. In particular,
the crossing properties of all straight-line segments
spanned by a planar $n$-point set are reflected by its
order type. We establish a complete and reliable data base
for all possible order types of size $n=10$ or less. The
data base includes a realizing point set for each order
type in small integer grid representation. To our
knowledge, no such project has been carried out before. We
substantiate the usefulness of our data base by applying it
to several problems in computational and combinatorial
geometry. Problems concerning triangulations, simple
polygonalizations, complete geometric graphs, and $k$-sets
are addressed. This list of possible applications is not
meant to be exhaustive. We believe our data base to be of
value to many researchers who wish to examine their
conjectures on small point configurations. }
}
@Article{aak-pc-02,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {Points and Combinatorics},
journal = {Special Issue on Foundations of Information Processing of
{TELEMATIK}},
pages = {12--17},
volume = 1,
year = {2002},
address = {Graz, Austria}
}
@TechReport{aak-prcn-01,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {Progress on rectilinear crossing numbers},
institution = {IGI-TU Graz, Austria},
year = 2002,
abstract = {Let $\overline{cr}(G)$ denote the rectilinear crossing
number of a graph $G$. We show $\overline{cr}(K_{11})=102$
and $\overline{cr}(K_{12})=153$. Despite the remarkable
hunt for the crossing number of the complete graph $K_n$,
initiated by R. Guy in the 1960s, these quantities have
been unknown for $n>10$ to date. We also establish new
upper and lower bounds on $\overline{cr}(K_{n})$ for $13
\leq n \leq 20$, along with an improved general lower bound
for $\overline{cr}(K_{n})$. The results mainly rely on
recent methods developed by the authors for exhaustively
enumerating all combinatorially inequivalent sets of points
(so-called order types). },
htmlnote = {See also our crossing
number homepage.}
}
@InProceedings{aaks-cmpt-02,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser and B.
Speckmann},
title = {Convexity Minimizes Pseudo-Triangulations},
booktitle = {Proc. $14th$ Annual Canadian Conference on Computational
Geometry CCCG 2002},
pages = {158--161},
year = 2002,
address = {Lethbridge, Alberta, Canada},
abstract = {For standard triangulations it is not known which sets of
points have the fewest or the most triangulations. In
contrast, we show that sets of points in convex position
minimize the number of minimum pseudo-triangulations. This
adds to the common belief that minimum
pseudo-triangulations are more tractable in many
respects.}
}
@Article{aaks-cmpt-03,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser and B.
Speckmann},
title = {Convexity Minimizes Pseudo-Triangulations},
journal = {Computational Geometry: Theory and Applications},
volume = {28},
pages = {3--10},
year = 2004,
abstract = {The number of minimum pseudo-triangulations is minimized
for point sets in convex position.}
}
@InProceedings{abdhkkrsu-ggt-03,
author = {O. Aichholzer and D. Bremner and E.D. Demaine and F.
Hurtado and E. Kranakis and H. Krasser and S. Ramaswami and
S. Sethia and J. Urrutia},
title = {Geometric Games on Triangulations},
booktitle = {Proc. $19^{th}$ European Workshop on Computationl Geometry
CG '03 Bonn },
pages = {89--92},
year = 2003,
address = {Bonn, Germany},
abstract = {We analyze several perfect-information combinatorial games
played on planar triangulations. We describe main broad
categories of these games and provide in various situations
polynomial-time algorithms to determine who wins a given
game under optimal play, and ideally, to find a winning
strategy. Relations to relevant existing combinatorial
games, such as Kayles, are also shown.}
}
@InProceedings{abdhkkrsu-pwt-02,
author = {O. Aichholzer and D. Bremner and E.D. Demaine and F.
Hurtado and E. Kranakis and H. Krasser and S. Ramaswami and
S. Sethia and J. Urrutia},
title = {Playing with Triangulations},
booktitle = {Proc. Japan Conference on Discrete and Computational
Geometry JCDCG 2002},
pages = {46--54},
year = 2002,
address = {Tokyo, Japan},
abstract = {We analyze several perfect-information combinatorial games
played on planar triangulations. We describe main broad
categories of these games and provide in various situations
polynomial-time algorithms to determine who wins a given
game under optimal play, and ideally, to find a winning
strategy. Relations to relevant existing combinatorial
games, such as Kayles, are also shown.}
}
@InProceedings{abdhkkrsu-pwt-03,
author = {O. Aichholzer and D. Bremner and E.D. Demaine and F.
Hurtado and E. Kranakis and H. Krasser and S. Ramaswami and
S. Sethia and J. Urrutia},
title = {Playing with Triangulations},
booktitle = {Lecture Notes in Computer Science 2866, Japanese
Conference, JCDCG 2002},
pages = {22--37},
year = 2003,
abstract = {We analyze several perfect-information combinatorial games
played on planar triangulations. We introduce three broad
categories of such games constructing, transforming and
marking triangulations. In various situations, we develop
polynomial-time algorithms to determine who wins a given
game under optimal play, and to find a winning strategy.
Along the way we show connections to existing combinatorial
games, such as Kayles.}
}
@Article{adk-flsvd-06,
author = {F. Aurenhammer and R.L.S.Drysdale and H. Krasser},
title = {Farthest line segment {V}oronoi diagrams},
journal = {Information Processing Letters},
year = 2006,
pages = {220--225},
volume = {100},
abstract = {The farthest line segment Voronoi diagram shows properties
different from both the closest-segment Voronoi diagram and
the farthest-point Voronoi diagram. Surprisingly, this
structure did not receive attention in the computational
geometry literature. We analyze its combinatorial and
topological properties and outline an $O(n \log n)$ time
construction algorithm that is easy to implement. No
restrictions are placed upon the~$n$ input line segments;
they are allowed to touch or cross.}
}
@InProceedings{ahk-twpst-04,
author = {O. Aichholzer and C. Huemer and H. Krasser},
title = {Triangulations Without Pointed Spanning Trees - Extended
Abstract},
booktitle = {Proc. $20^{th}$ European Workshop on Computational
Geometry EWCG '04},
year = 2004,
pages = {221--224},
address = {Sevilla, Spain},
abstract = {Problem $50$ in the Open Problems Project~\cite{OPP} asks
whether any triangulation on a point set in the plane
contains a pointed spanning tree as a subgraph. We provide
a counterexample. As a consequence we show that there exist
triangulations which require a linear number of edge flips
to become Hamiltonian. }
}
@Article{ak-psclcf-06,
author = {F. Aurenhammer and H. Krasser},
title = {Pseudo-simplicial complexes from maximal locally convex
functions},
journal = {Discrete \& Computional Geometry},
year = 2006,
pages = {201--221},
volume = 35,
abstract = {We introduce and discuss pseudo-simplicial complexes
in~$R^d$ as generalizations of pseudo-triangulations
in~$R^2$. Our approach is based on the concept of maximal
locally convex functions on polytopal domains.}
}
@InProceedings{ak-psotd-01,
author = {O. Aichholzer and H. Krasser},
title = {The Point Set Order Type Data Base: A Collection of
Applications and Results},
booktitle = {Proc. $13th$ Annual Canadian Conference on Computational
Geometry CCCG 2001},
pages = {17--20},
year = 2001,
address = {Waterloo, Ontario, Canada},
htmlnote = {See also our order
type homepage.},
abstract = {Order types are a common tool to provide the combinatorial
structure of point sets in the plane. For many problems in
combinatorial and computational geometry only the order
type of the underlying point set has to be considered.
Recently a complete order type data base of $n$-point sets
has been developed for $n\leq 10$, which gives a way to
examine the combinatorial properties of all possible point
sets for fixed size $n$. Based on this result we present
applications and results for problems concerning
intersection properties, convexity, crossing-free straight
line graphs, and others, thus confirming or disproving
several conjectures on these topics. Besides providing
concrete results the aim of this work is to stimulate
further research by revealing structural relations of
extreme examples for $17$ geometrical and combinatorial
problems.}
}
@InProceedings{ak-ptc-05,
author = {F. Aurenhammer and H. Krasser},
title = {Pseudo-tetrahedral complexes},
booktitle = {Proc. $21^{st}$ European Workshop on Computational
Geometry EuroCG '05},
pages = {85--88},
year = 2005,
address = {Eindhoven, The Netherlands},
abstract = {Pseudo-triangulations are interesting and flexible
generalizations of triangulations that have found their
place in computational geometry. Unlike triangulations,
pseudo-triangulations eluded a meaningful generalization to
higher dimensions so far. In this paper, we define
pseudo-simplices and pseudo-simplicial complexes in d-space
in a way consistent to pseudo-triangulations in the plane.
Flip operations in pseudo-complexes are specified, as
combinations of flips in pseudo-triangulations, and of
bistellar flips in simplicial complexes. Our results are
based on the concept of maximal locally convex functions on
polyhedral domains, that allows us to unify several
well-known structures, namely pseudo-triangulations,
constrained Delaunay triangulations, and regular simplicial
complexes.}
}
@MastersThesis{k-ktep-99,
author = {H. Krasser},
title = {Kompatible Triangulierungen ebener Punktmengen},
note = {(in German)},
school = {Institute for Theoretical Computer Science, Graz
University of Technology, Austria},
year = 1999,
month = {June},
keywords = {computational geometry, triangulations, compatible,
isomorphic},
abstract = {Triangulations are very important in computational
geometry, since a lot of algorithms make use of this data
structure. The subject of this thesis is the special
problem of compatible triangulations. The original
motivation to investigate this problem comes from
cartography. Two point sets in the plane are called
compatible if isomorphic triangulations exist. First the
structure of the convex hulls of compatible triangulations
is analyzed in the case of edge-compatibility. Then it is
shown that triangle-compatibility simplifies the situation.
A connection to lambda-matrices is also given. If two point
sets have the same lambda-matrices then every triangulation
of one point set admits a compatible triangulation of the
other point set. At last the main conjecture on compatible
triangulations, namely that every two point sets of same
cardinality in general position that have an identical
number of points on the convex hulls admit compatible
triangulations, is proved for some special cases. }
}
@PhDThesis{k-otpsp-03,
author = {H. Krasser},
title = {Order Types of Point Sets in the Plane},
school = {Institute for Theoretical Computer Science, Graz
University of Technology, Austria},
year = 2003,
month = {October},
keywords = {computational geometry, combinatorial geometry, order
types, point sets, pseudoline arrangements, rectilinear
crossing number, triangulation, pseudo-triangulation},
abstract = {Order types are a means to characterize the combinatorial
properties of a finite point set in the plane. In
particular, the crossing properties of all straight-line
segments spanned by a point configuration are reflected by
its order type. We establish a complete and reliable data
base for all different order types of size up to $11$. To
the best of our knowledge, such a project has not been
carried out before, not even for point sets of smaller
size. We discuss several applications of this data base and
related techniques to prominent problems in computational
and combinatorial geometry. These include problems on
crossing-free graphs like triangulations or simple
polygonalizations, but also general crossing problems like
the rectilinear crossing number.}
}