@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{a-aagt-88,
  author	= {F. Aurenhammer},
  title		= {Algorithmic aspects of {G}ale transforms (abstract)},
  booktitle	= {Proc. $13^{th}$ 3-Ann. Int'l Symp. Mathematical
		  Programming},
  pages		= 176,
  year		= 1988,
  address	= {Tokyo, Japan}
}

@Article{a-caecc-87,
  author	= {F. Aurenhammer},
  title		= {A criterion for the affine equivalence of cell complexes
		  in {$R^d$} and convex polyhedra in {$R^{d+1}$}},
  journal	= {Discrete \& Computational Geometry},
  year		= 1987,
  volume	= 2,
  number	= 1,
  pages		= {49--64},
  note		= {[IIG-Report-Series 205, TU Graz, Austria, 1985]},
  abstract	= {A criterion is gives that decides, for a convex tiling $C$
		  of $R^d$, whether $C$ is the projection of the faces in the
		  boundary of some convex polyhedron $P$ in $R^{d+1}$. Its
		  applicability is restricted neither by the properties nor
		  by the dimension of $C$. It turns out to be simpler than
		  other criteria and allows the easy examination of various
		  classes of cell complexes. In addition, the criterion is
		  constructive, that is, it can be used to construct $P$
		  provided it exists.}
}

@Article{a-cgeqr-01,
  author	= {F. Aurenhammer},
  title		= {Computational geometry -- some easy questions and their
		  recent solutions},
  journal	= {J. Universal Computer Science},
  year		= 2001,
  volume	= 7,
  pages		= {338--354},
  note		= {Special Issue.},
  abstract	= {We address three basic questions in computational geometry
		  which can be phrased in simple terms but have only recently
		  received (more or less) satisfactory answers: point set
		  enumeration, optimum triangulation, and polygon
		  decomposition.}
}

@InProceedings{a-gcvtp-93,
  author	= {F. Aurenhammer},
  title		= {Geometric clustering and {V}oronoi-type partitions},
  booktitle	= {$16^{th}$ IFIP Conf. System Modelling and Optimization},
  year		= 1993,
  pages		= {93-94},
  address	= {Compiegne, France}
}

@Article{a-gefsi-95,
  author	= {F. Aurenhammer},
  title		= {Guest editor's foreword of the special issue on
		  computational geometry},
  journal	= {Int'l Journal of Computational Geometry \& Applications},
  year		= 1995,
  volume	= {5},
  pages		= {1}
}

@TechReport{a-gpd-83,
  author	= {F. Aurenhammer},
  title		= {On the generality of power diagrams},
  institution	= {TU Graz, Austria},
  year		= 1983,
  type		= {IIG Report},
  number	= {F126},
  abstract	= {A set $s = \{ x \mid <x-z>^2 = r^2 \}$ in Euclidean space
		  is called a sphere with center $z$ and positive radius $r$.
		  For an arbitrary point $x$, $<x-z>^2 = r^2$ is the power of
		  $x$ with respect to $s$. Extending these concepts to
		  imaginary radii, they are exploited to show the equivalence
		  of two types of cell complexes: those that can be obtained
		  by projection of convex polyhedra, and those that come from
		  projecting levels in arrangement of hyperplanes. As a
		  consequence, higher-order Voronoi diagrams can be
		  constructed by determining a convex hull.}
}

@InProceedings{a-gv-85,
  author	= {F. Aurenhammer},
  title		= {Gewichtete {V}oronoidiagramme},
  booktitle	= {Workshop on Computational Geometry CG '85},
  year		= 1985,
  address	= {Karlsruhe, Germany}
}

@PhDThesis{a-gvdgd-84,
  author	= {F. Aurenhammer},
  title		= {Gewichtete {V}oronoi {D}iagramme: {G}eometrische {D}eutung
		  und {K}onstruktions-{A}lgorithmen},
  school	= {IIG-TU Graz, Austria},
  year		= 1984,
  note		= {Report B53},
  abstract	= {Das oft als Computational Geometry bezeichnete Teilgebiet
		  der Computerwissenschaften beschaeftigt sich mit der
		  algorithmischen Loesung elementargeometrischer Probleme.
		  Einen Schwerpunkt in der Computational Geometry bildet die
		  Untersuchung von Abstandsproblemen. In diesem Zusammenhang
		  spielt das Voronoi Diagramm einer endlichen Punktmenge eine
		  zentrale Rolle. Die vorliegende Arbeit ist eine
		  geometrische und algorithmische Studie sogenannter
		  gewichteter Voronoi Diagramme. Diese Diagramme leiten sich
		  aus dem Original durch Ersetzen des Euklidabstandes durch
		  individuell gewichtete Abstaende her. Das
		  Anwendungsspektrum solcher Konzepte umfasst die
		  Wissenschaften Geographie, Oekonomie, Biologie, Mathematik,
		  Physik und Chemie. Die Hauptergebnisse dieser Arbeit sind
		  die Erforschung der Verwandtschaft gewichteter Diagramme zu
		  anderen geometrischen Objekten (konvexe Huellen,
		  Zellkomplexe und Arrangements) mit Hilfe geometrischer
		  Transformationen, und der Entwurf effizienter Algorithmen
		  fuer ihre Konstruktion. Ein Teil der Resultate wurde
		  bereits in Schnelldruckserien und wissenschaftlichen
		  Journalen veroeffentlicht.}
}

@Article{a-iadbu-88,
  author	= {F. Aurenhammer},
  title		= {Improved algorithms for discs and balls using power
		  diagrams},
  journal	= {Journal of Algorithms},
  year		= 1988,
  volume	= 9,
  number	= 2,
  pages		= {151--161},
  note		= {[IIG-Report-Series 209, TU Graz, Austria, 1985]},
  abstract	= {The properties of a particular generalization of Voronoi
		  diagrams called power diagrams are exploited to obtain new
		  and improved algorithms for union, intersection, and
		  measure problems for discs and balls.}
}

@InProceedings{a-jschc-87,
  author	= {F. Aurenhammer},
  title		= {{J}ordan sorting via convex hulls of certain non-simple
		  polygons},
  booktitle	= {Proc. $3^{rd}$ Ann. ACM Symp. Computational Geometry},
  pages		= {21--29},
  year		= 1987,
  address	= {Waterloo, Canada}
}

@Article{a-lcpd-88,
  author	= {F. Aurenhammer},
  title		= {Linear combinations from power domains},
  journal	= {Geometriae Dedicata},
  year		= 1988,
  volume	= 28,
  pages		= {45--52},
  note		= {[IIG-Report-Series 243, TU Graz, Austria, 1987]},
  abstract	= {The well-known concept of power domains defined via
		  subsets of a finite set $S$ of weighted points in $R^d$ is
		  exploited to obtain various linear combinations among the
		  points in $S$. This generalizes a result of Sibson who
		  considered the special case of singleton subsets and
		  unweighted points.}
}

@InProceedings{a-ndrcv-86,
  author	= {F. Aurenhammer},
  title		= {A new duality result concerning {V}oronoi diagrams},
  booktitle	= {Proc. $13^{th}$ Ann. ICALP, Lecture Notes in Computer
		  Science},
  pages		= {21--32},
  year		= 1986,
  volume	= 226,
  address	= {Rennes, France},
  publisher	= {Springer Verlag},
  abstract	= {A new duality between order-$k$ Voronoi diagrams in $E^d$
		  and convex hulls in $E^{d+1}$ is established. It implies a
		  reasonably simple algorithm for computing the order-$k$
		  Voronoi diagram for $n$ points in the palne in $O(k^2 n
		  \log n)$ time and optimal $O(k(n-k))$ space.}
}

@Article{a-ndrcv-90,
  author	= {F. Aurenhammer},
  title		= {A new duality result concerning {V}oronoi diagrams},
  journal	= {Discrete \& Computational Geometry},
  year		= 1990,
  volume	= 5,
  number	= 3,
  pages		= {243--254},
  note		= {[IIG-Report-Series 216, TU Graz, Austria, 1985]},
  abstract	= {A new duality between order-$k$ Voronoi diagrams in $E^d$
		  and convex hulls in $E^{d+1}$ is established. It implies a
		  reasonably simple algorithm for computing the order-$k$
		  Voronoi diagram for $n$ points in the palne in $O(k^2 n
		  \log n)$ time and optimal $O(k(n-k))$ space.}
}

@Article{a-odwvd-86,
  author	= {F. Aurenhammer},
  title		= {The one-dimensional weighted {V}oronoi diagram},
  journal	= {Information Processing Letters},
  year		= 1986,
  volume	= 22,
  number	= 3,
  pages		= {119--123},
  note		= {[IIG-Report-Series F110, TU Graz, Austria, 1983]}
}

@Article{a-olsts-88a,
  author	= {F. Aurenhammer},
  title		= {On-line sorting of twisted sequences in linear time},
  journal	= {BIT},
  year		= 1988,
  volume	= 28,
  pages		= {194--204},
  note		= {[IIG-Report-Series 232, TU Graz, Austria, 1987]},
  abstract	= {A sequence of real numbers is called twisted if it can be
		  produced from the sorted sequence by repeatedly reversing
		  the order of consecutive subsequences. It is shown that
		  twisted sequences constitute a class of exponentially many
		  members each of which can be recognized and sorted, by a
		  simple on-line algorithm, in linear time.}
}

@InProceedings{a-olsts-88b,
  author	= {F. Aurenhammer},
  title		= {On-line sorting of twisted sequences in linear time},
  booktitle	= {$2^{nd}$ Workshop on Computational Geometry and Discrete
		  Algorithms},
  year		= 1988,
  address	= {Osaka, Japan}
}

@Article{a-pdpaa-87,
  author	= {F. Aurenhammer},
  title		= {Power diagrams: properties, algorithms, and applications},
  journal	= {SIAM Journal on Computing},
  year		= 1987,
  volume	= 16,
  number	= 1,
  pages		= {78--96},
  note		= {[IIG-Report-Series F120, TU Graz, Austria, 1983]},
  abstract	= {The power $pow(x,s)$ of a point $x$ with respect to a
		  sphere $s$ in Euclidean $d$-space $E^d$ is given by
		  $d^2(x,z)-r^2$, where $d$ denotes the Euclidean distance
		  function, and $z$ and $r$ are the center and the radius of
		  $s$. The power diagram of a finite set $S$ of spheres in
		  $E^d$ is a cell complex that associates each $s \in S$ with
		  the convex domain $\{x \in E^d \mid pow(x,s) < pow(x,t),
		  \mbox{for all} t \in S - \{s\} \}$. The close relationship
		  to convex hulls and arrangements of hyperplanes is
		  investigated and exploited. Efficient algorithms that
		  compute the power diagram and its order-$k$ modifications
		  are obtained. Among the applications of these results are
		  algorithms for detecting $k$-sets, for union and
		  intersection problems for cones and paraboloids, and for
		  constructing weighted Voronoi diagrams and Voronoi diagrams
		  for spheres. Upper space bounds for these geometric
		  problems are derived.}
}

@InProceedings{a-pgdtf-05,
  author	= {F. Aurenhammer},
  title		= {Pre-triangulations: A generalization of {D}elaunay
		  triangulations and flips},
  booktitle	= {$2^{nd}$ Intern. Symp. on Voronoi Diagrams in Science and
		  Engineering},
  pages		= {235},
  year		= 2005,
  address	= {Hanyang University, Seoul, Korea},
  note		= {(plenar talk)}
}

@InProceedings{a-psd-03,
  author	= {F. Aurenhammer},
  title		= {Pseudo-simplices and their derivation},
  booktitle	= {Voronoi Conference on Analytic Number Theory and Spatial
		  Tesselations},
  pages		= {11},
  year		= 2003,
  address	= {Inst. Math. National Academy of Sciences, Kiev, Ukraine}
}

@Article{a-rbgtv-90,
  author	= {F. Aurenhammer},
  title		= {A relationship between {G}ale transforms and {V}oronoi
		  diagrams},
  journal	= {Discrete Applied Mathematics},
  year		= 1990,
  volume	= 28,
  pages		= {83--91},
  note		= {[IIG-Report-Series 247, TU Graz, Austria, 1988]},
  abstract	= {Gale transforms and Voronoi diagrams for finite point sets
		  in $R^d$ are two structures well known in discrete and
		  computational geometry. It is shown that they are related
		  in the sense that Gale transforms of a point set can be
		  computed from (generalizations of) its Voronoi diagram.}
}

@Article{a-rpccc-87,
  author	= {F. Aurenhammer},
  title		= {Recognizing polytopical cell complexes and constructing
		  projection polyhedra},
  journal	= {Journal of Symbolic Computation},
  year		= 1987,
  volume	= 3,
  number	= 3,
  pages		= {249--255},
  note		= {[IIG-Report-Series 203, TU Graz, Austria, 1985]},
  abstract	= {A simple cell complex $C$ in Euclidean $d$-space $E^d$ is
		  a covering of $E^d$ by finitely many convex $j$-dimensional
		  polyhedra (the $j$-faces of $C$), each of which is in the
		  closure of exactly $d-j+1$ $d$-faces of $C$. An algorithm
		  that recognises when $C$ is the projection of the set of
		  faces bounding some convex polyhedron $P(C)$ in $E^{d+1}$,
		  and that constructs $P(C)$ provided its existence is
		  outlined. The method is optimal at least for $d=2$. No
		  complexity results were previously known for both problems.
		  The results have applications in statics, to the
		  recognition of Voronoi diagrams, and to planar point
		  location.}
}

@InProceedings{a-ugtcg-88,
  author	= {F. Aurenhammer},
  title		= {Using {G}ale transforms in computational geometry},
  booktitle	= {Proc. $4^{th}$ Workshop on Computational Geometry CG '88,
		  Lecture Notes in Computer Science},
  pages		= {202--216},
  year		= 1988,
  volume	= 333,
  address	= {Wuerzburg, Germany},
  publisher	= {Springer Verlag},
  abstract	= {Let $P$ denote a set of $n \geq d+1$ points in $d$-space
		  $R^d$. A Gale transform of $P$ assigns to each point in $P$
		  a vector in space $R^{d+1}$ such that the resulting
		  $n$-tuple of vectors reflects all affinely invariant
		  properties of $P$. First utilized by Gale in the 1950s,
		  Gale transforms have been recognized as a powerful tool in
		  combinatorial geometry. This paper introduces Gale
		  transforms to computational geometry. It offers a direct
		  algorithm for their construction and sketches applications
		  to convex hull and visibility problems. An application to
		  scene analysis is worked out in some more detail.}
}

@Article{a-ugtcg-91,
  author	= {F. Aurenhammer},
  title		= {Using {G}ale transforms in computational geometry},
  journal	= {Mathematical Programming},
  year		= 1991,
  volume	= {B 52},
  pages		= {179--190},
  note		= {Special Issue. [IIG-Report-Series 248, TU Graz, Austria,
		  1988]},
  abstract	= {Let $P$ denote a set of $n \geq d+1$ points in $d$-space
		  $R^d$. A Gale transform of $P$ assigns to each point in $P$
		  a vector in space $R^{d+1}$ such that the resulting
		  $n$-tuple of vectors reflects all affinely invariant
		  properties of $P$. First utilized by Gale in the 1950s,
		  Gale transforms have been recognized as a powerful tool in
		  combinatorial geometry. This paper introduces Gale
		  transforms to computational geometry. It offers a direct
		  algorithm for their construction and addresses applications
		  to convex hull and visibility problems. An application to
		  scene analysis is worked out in detail.}
}

@Article{a-vdsfg-91a,
  author	= {F. Aurenhammer},
  title		= {{V}oronoi diagrams -- a survey of a fundamental geometric
		  data structure},
  journal	= {ACM Computing Surveys},
  year		= 1991,
  volume	= 23,
  number	= 3,
  pages		= {345--405},
  note		= {{H}abilitationsschrift. [Report B 90-09, FU Berlin,
		  Germany, 1990]},
  abstract	= {This paper presents a survey of the Voronoi diagram, one
		  of the most fundamental data structures in computational
		  geometry. It demonstrates the importance and usefulness of
		  the Voronoi diagram in a wide variety of fields inside and
		  outside computer science and surveys the history of its
		  development. The paper puts particular emphasis on the
		  unified exposition of its mathematical and algorithmic
		  properties. Finally, the paper provides the first
		  comprehensive bibliography on Voronoi diagrams and related
		  structures.}
}

@Article{a-vdsfg-91b,
  author	= {F. Aurenhammer},
  title		= {{V}oronoi diagrams -- a survey of a fundamental geometric
		  data structure},
  journal	= {bit acm computing surveys '91 (Japanese translation),
		  Kyoritsu Shuppan Co., Ltd.},
  year		= 1993,
  pages		= {131--185}
}

@Article{a-wsfsd-07,
  author	= {F. Aurenhammer},
  title		= {Weighted skeletons and fixed-share decomposition},
  journal	= {Computational Geometry: Theory and Applications},
  year		= {2007},
  volume	= {40},
  pages		= {93-101},
  abstract	= {We introduce the concept of weighted skeleton of a polygon
		  and present various decomposition and optimality results
		  for this skeletal structure when the underlying polygon is
		  convex.}
}

@InProceedings{aa-chh-94,
  author	= {O. Aichholzer and F. Aurenhammer},
  title		= {Classifying hyperplanes in hypercubes},
  booktitle	= {Proc. $10^{th}$ European Workshop on Computational
		  Geometry CG '94},
  pages		= {53--57},
  year		= 1994,
  address	= {Santander, Spain},
  abstract	= {We consider hyperplanes spanned by vertices of the unit
		  $d$-cube. We classify these hyperplanes by parallelism to
		  coordinate axes, by symmetry of the $d$-cube vertices they
		  avoid, as well as by so-called hull-honesty. (Hull-honest
		  hyperplanes are those whose intersection figure with the
		  $d$-cube coincides with the convex hull of the $d$-cube
		  vertices they contain; they do not cut $d$-cube edges
		  properly.) We describe relationships between these classes,
		  and give the exact number of hull-honest hyperplanes, in
		  general dimensions. An experimental enumeration of all
		  spanned hyperplanes up to dimension eight showed us the
		  intrinsic difficulty of developing a general enumeration
		  scheme. Motivation for considering such hyperplanes stems
		  from coding theory, from linear programming, and from the
		  theory of machine learning.}
}

@Article{aa-chh-96,
  author	= {O. Aichholzer and F. Aurenhammer},
  title		= {Classifying hyperplanes in hypercubes},
  journal	= {SIAM Journal on Discrete Mathematics},
  year		= 1996,
  volume	= 9,
  number	= 2,
  pages		= {225--232},
  note		= {[IIG-Report-Series 408, TU Graz, Austria, 1995]},
  abstract	= {We consider hyperplanes spanned by vertices of the unit
		  $d$-cube. We classify these hyperplanes by parallelism to
		  coordinate axes, by symmetry of the $d$-cube vertices they
		  avoid, as well as by so-called hull-honesty. (Hull-honest
		  hyperplanes are those whose intersection figure with the
		  $d$-cube coincides with the convex hull of the $d$-cube
		  vertices they contain; they do not cut $d$-cube edges
		  properly.) We describe relationships between these classes,
		  and give the exact number of hull-honest hyperplanes, in
		  general dimensions. An experimental enumeration of all
		  spanned hyperplanes up to dimension eight showed us the
		  intrinsic difficulty of developing a general enumeration
		  scheme. Motivation for considering such hyperplanes stems
		  from coding theory, from linear programming, and from the
		  theory of machine learning.}
}

@InProceedings{aa-ssgpf-96,
  author	= {O. Aichholzer and F. Aurenhammer},
  title		= {Straight skeletons for general polygonal figures},
  booktitle	= {Proc. $2^{nd}$ Ann. Int'l. Computing and Combinatorics
		  Conf. COCOON'96, Lecture Notes in Computer Science},
  pages		= {117--126},
  year		= 1996,
  volume	= 1090,
  address	= {Hong Kong},
  publisher	= {Springer Verlag},
  note		= {[IIG-Report-Series 423, TU Graz, Austria, 1995]},
  abstract	= {A novel type of skeleton for general polygonal figures,
		  the straight skeleton $S(G)$ of a planar straight line
		  graph $G$, is introduced and discussed. Exact bounds on the
		  size of $S(G)$ are derived. The straight line structure of
		  $S(G)$ and its lower combinatorial complexity may make
		  $S(G)$ preferable to the widely used Voronoi diagram (or
		  medial axis) of $G$ in several applications. We explain why
		  $S(G)$ has no Voronoi diagram based interpretation and why
		  standard construction techniques fail to work. A simple
		  $O(n)$ space algorithm for constructing $S(G)$ is proposed.
		  The worst-case running time is $O(n^3 \log n)$, but the
		  algorithm can be expected to be practically efficient, and
		  it is easy to implement. We also show that the concept of
		  $S(G)$ is flexible enough to allow an individual weighting
		  of the edges and vertices of $G$, without changes in the
		  maximal size of $S(G)$, or in the method of construction.
		  Apart from offering an alternative to Voronoi-type
		  skeletons, these generalizations of $S(G)$ have
		  applications to the reconstruction of a geographical
		  terrain from a given river map, and to the construction of
		  a polygonal roof above a given layout of ground walls.}
}

@InCollection{aa-ssgpf-98,
  author	= {O. Aichholzer and F. Aurenhammer},
  title		= {Straight skeletons for general polygonal figures in the
		  plane},
  booktitle	= {Voronoi's Impact on Modern Sciences II},
  pages		= {7--21},
  publisher	= {Proc. Institute of Mathematics of the National Academy of
		  Sciences of Ukraine},
  year		= 1998,
  editor	= {A.M. Samoilenko},
  volume	= 21,
  address	= {Kiev, Ukraine},
  abstract	= {A novel type of skeleton for general polygonal figures,
		  the straight skeleton $S(G)$ of a planar straight line
		  graph $G$, is introduced and discussed. Exact bounds on the
		  size of $S(G)$ are derived. The straight line structure of
		  $S(G)$ and its lower combinatorial complexity may make
		  $S(G)$ preferable to the widely used Voronoi diagram (or
		  medial axis) of $G$ in several applications. We explain why
		  $S(G)$ has no Voronoi diagram based interpretation and why
		  standard construction techniques fail to work. A simple
		  $O(n)$ space algorithm for constructing $S(G)$ is proposed.
		  The worst-case running time is $O(n^3 \log n)$, but the
		  algorithm can be expected to be practically efficient, and
		  it is easy to implement. We also show that the concept of
		  $S(G)$ is flexible enough to allow an individual weighting
		  of the edges and vertices of $G$, without changes in the
		  maximal size of $S(G)$, or in the method of construction.
		  Apart from offering an alternative to Voronoi-type
		  skeletons, these generalizations of $S(G)$ have
		  applications to the reconstruction of a geographical
		  terrain from a given river map, and to the construction of
		  a polygonal roof above a given layout of ground walls.}
}

@Article{aa-vdcgf-02,
  author	= {O. Aichholzer and F. Aurenhammer},
  title		= {Voronoi Diagrams - Computational Geometry's Favorite},
  journal	= {Special Issue on Foundations of Information Processing of
		  {TELEMATIK}},
  pages		= {7--11},
  volume	= 1,
  year		= {2002},
  address	= {Graz, Austria}
}

@InProceedings{aaacjr-at-10,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and K.
		  \v{C}ech Dobi\.a\v{s}ov\.a and B. J\"uttler and G. Rote},
  title		= {Arc triangulations},
  booktitle	= {Proc. $26^{th}$ European Workshop on Computational
		  Geometry EuroCG '2010},
  pages		= {17--20},
  year		= 2010,
  address	= {Dortmund, Germany},
  abstract	= {An important objective in the choice of a triangulation of
		  a given point set is that the smallest angle becomes as
		  large as possible. In the straight line case, it is known
		  that the Delaunay triangulation is optimal in this respect.
		  We propose and study the concept of a circular arc
		  triangulation, a simple and effective alternative that
		  offers flexibility for additionally enlarging small angles.
		  We show that angle optimization and related questions lead
		  to linear programming problems that can be formulated as
		  simple graph-theoretic problems, and we define flipping
		  operations in arc triangles. Moreover, special classes of
		  arc triangulations are considered, for applications in
		  finite element methods and graph drawing.}
}

@InProceedings{aaj-otap-12,
  author	= {W. Aigner and F. Aurenhammer and B. J\"uttler},
  title		= {On triangulation axes of polygons},
  booktitle	= {Proc. $28^{th}$ European Workshop on Computational
		  Geometry EuroCG '2012},
  pages		= {125--128},
  year		= 2012,
  address	= {Assisi, Italy},
  abstract	= {We define the \textit{triangulation axis} of a simple
		  polygon~$P$ as an anisotropic medial axis of~$P$ whose
		  `unit disks' are line segments or triangles. The underlying
		  triangulation that specifies the anisotropy can be varied,
		  to adapt the axis so as to reflect predominant geometrical
		  and topological features of~$P$. Triangulation axes are
		  piecewise linear skeletons, and typically have much fewer
		  edges and branchings than the Euclidean medial axis or the
		  straight skeleton of~$P$ (between $n-2$ and $2n-6$ edges,
		  compared to $2n-3$). Still, they retain important
		  properties, as for example the reconstructability of~$P$
		  from its skeleton. Triangulation axes can be easily
		  computed from their defining triangulations in $O(n)$ time.
		  We investigate the effect of using several optimal
		  triangulations for~$P$. In particular, careful edge
		  flipping in the constrained Delaunay triangulation leads,
		  in $O(n \log n)$ overall time, to an axis competitive to
		  high quality axes requiring $O(n^3)$ time for optimization
		  via dynamic programming.}
}

@InProceedings{aaacjr-twca-11,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and K.
		  \v{C}ech Dobi\.a\v{s}ov\.a and B. J\"uttler and G. Rote},
  title		= {Triangulations with circular arcs},
  booktitle	= {Proc. $19^{th}$ Int. Symposium on Graph Drawing, Springer
		  LNCS},
  volume	= 7034,
  pages		= {296--307},
  year		= 2011,
  address	= {Eindhoven, Netherlands},
  abstract	= {An important objective in the choice of a triangulation is
		  that the smallest angle becomes as large as possible. In
		  the straight line case, it is known that the Delaunay
		  triangulation is optimal in this respect. We propose and
		  study the concept of a circular arc triangulation---a
		  simple and effective alternative that offers flexibility
		  for additionally enlarging small angles---and discuss its
		  applications in graph drawing.}
}

@Article{aaag-ntsp-95,
  author	= {O. Aichholzer and D. Alberts and F. Aurenhammer and B.
		  Gaertner},
  title		= {A novel type of skeleton for polygons},
  journal	= {Journal of Universal Computer Science},
  year		= 1995,
  volume	= 1,
  number	= 12,
  pages		= {752--761},
  htmlnote	= {Click here for the <A
		  HREF="http://www.iicm.edu/jucs_1_12/a_novel_type_of">Online
		  Version</A>},
  note		= {[IIG-Report-Series 424, TU Graz, Austria, 1995]},
  abstract	= {A new internal structure for simple polygons, the straight
		  skeleton, is introduced and discussed. It is composed of
		  pieces of angular bisectores which partition the interior
		  of a given $n$-gon $P$ in a tree-like fashion into $n$
		  monotone polygons. Its straight-line structure and its
		  lower combinatorial complexity may make the straight
		  skeleton preferable to the widely used medial axis of a
		  polygon. As a seemingly unrelated application, the straight
		  skeleton provides a canonical way of constructing a
		  polygonal roof above a general layout of ground walls.}
}

@InProceedings{aaag-sssp-95,
  author	= {O. Aichholzer and D. Alberts and F. Aurenhammer and B.
		  Gaertner},
  title		= {Straight skeletons of simple polygons},
  booktitle	= {Proc. $4^{th}$ Int. Symp. of LIESMARS},
  pages		= {114--124},
  year		= 1995,
  address	= {Wuhan, P. R. China},
  abstract	= {A new internal structure for simple polygons, the straight
		  skeleton, is introduced and discussed. It is a tree and
		  partitions the interior of a given $n$-gon $P$ into $n$
		  monotone polygons, one for each edge of $P$. Its
		  straight-line structure and its lower combinatorial
		  complexity may make the straight skeleton $S(P)$ preferable
		  to the widely used medial axis of $P$. We show that $S(P)$
		  has no Voronoi diagram structure and give an $O(n r \log
		  n)$ time and $O(n)$ space construction algorithm, where $r$
		  counts the reflex vertices of $P$. As a seemingly unrelated
		  application, the straight skeleton provides a canonical way
		  of constructing a roof of given slope above a polygonal
		  layout of ground walls.}
}

@InProceedings{aaahjpr-dcvdr-09,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
		  Hackl and B. J\"uttler and E. Pilgerstorfer and M. Rabl},
  title		= {Divide-and conquer for {V}oronoi diagrams revisited},
  booktitle	= {Proc. $25^{th}$ Ann. ACM Symp. Computational Geometry},
  address	= {Aarhus, Denmark},
  pages		= {189--197},
  year		= 2009,
  abstract	= {We show how to divide the edge graph of a Voronoi diagram
		  into a tree that corresponds to the medial axis of an
		  (augmented) planar domain. Division into base cases is then
		  possible, which, in the bottom-up phase, can be merged by
		  trivial concatenation. The resulting construction
		  algorithm---similar to Delaunay triangulation methods---is
		  not bisector-based and merely computes dual links between
		  the sites, its atomic steps being inclusion tests for sites
		  in circles. This guarantees computational simplicity and
		  numerical stability. Moreover, no part of the Voronoi
		  diagram, once constructed, has to be discarded again. The
		  algorithm works for polygonal and curved objects as sites
		  and, in particular, for circular arcs which allows its
		  extension to general free-form objects by Voronoi diagram
		  preserving and data saving biarc approximations. The
		  algorithm is randomized, with expected runtime $O(n\logn)$
		  under certain assumptions on the input data. Experiments
		  substantiate an efficient behavior even when these
		  assumptions are not met. Applications to offset
		  computations and motion planning for general objects are
		  described.}
}

@Article{aaahjpr-dcvdr-10,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
		  Hackl and B. J\"uttler and E. Pilgerstorfer and M. Rabl},
  title		= {Divide-and conquer for {V}oronoi diagrams revisited},
  journal	= {Computational Geometry: Theory and Applications},
  volume	= {43},
  pages		= {688-699},
  year		= 2010,
  abstract	= {We show how to divide the edge graph of a Voronoi diagram
		  into a tree that corresponds to the medial axis of an
		  (augmented) planar domain. Division into base cases is then
		  possible, which, in the bottom-up phase, can be merged by
		  trivial concatenation. The resulting construction
		  algorithm---similar to Delaunay triangulation methods---is
		  not bisector-based and merely computes dual links between
		  the sites, its atomic steps being inclusion tests for sites
		  in circles. This guarantees computational simplicity and
		  numerical stability. Moreover, no part of the Voronoi
		  diagram, once constructed, has to be discarded again. The
		  algorithm works for polygonal and curved objects as sites
		  and, in particular, for circular arcs which allows its
		  extension to general free-form objects by Voronoi diagram
		  preserving and data saving biarc approximations. The
		  algorithm is randomized, with expected runtime $O(n\logn)$
		  under certain assumptions on the input data. Experiments
		  substantiate an efficient behavior even when these
		  assumptions are not met. Applications to offset
		  computations and motion planning for general objects are
		  described.}
}

@InProceedings{aaahjpr1-dcvdr-09,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
		  Hackl and B. J\"uttler and E. Pilgerstorfer and M. Rabl},
  title		= {Divide-and conquer for {V}oronoi diagrams revisited},
  booktitle	= {Proc. $25^{th}$ European Workshop on Computational
		  Geometry EuroCG'09},
  address	= {Brussels, Belgium},
  pages		= {293--296},
  year		= 2009,
  abstract	= {We propose a simple and practical divide-and-conquer
		  algorithm for constructing planar Voronoi diagrams. The
		  novel aspect of the algorithm is its emphasis on the
		  top-down phase, which makes it applicable to sites of
		  general shape.}
}

@Article{aaahjr-macpffs-08,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
		  Hackl and B. Juettler and M. Rabl},
  title		= {Medial axis computation for planar free-form shapes},
  journal	= {Computer Aided Design},
  year		= 2009,
  volume	= 41,
  pages		= {339--349},
  note		= {Special Issue},
  abstract	= {We present a simple, efficient, and stable method for
		  computing---with any desired precision---the medial axis of
		  simply connected planar domains. The domain boundaries are
		  assumed to be given as polynomial spline curves. Our
		  approach combines known results from the field of geometric
		  approximation theory with a new algorithm from the field of
		  computational geometry. Challenging steps are (1) the
		  approximation of the boundary spline such that the medial
		  axis is geometrically stable, and (2) the efficient
		  decomposition of the domain into base cases where the
		  medial axis can be computed directly and exactly. We solve
		  these problems via spiral biarc approximation and a
		  randomized divide \& conquer algorithm.}
}

@InProceedings{aaaj-emactsrplm-11,
  author	= {O. Aichholzer and W. Aigner and F. Aurenhammer and B.
		  J\"uttler},
  title		= {Exact medial axis computation for triangulated solids with
		  respect to piecewise linear metrics},
  booktitle	= {Proc. Int. Conf. Curves and Surfaces, Springer LNCS},
  address	= {Avignon, France},
  year		= 2011,
  volume	= 6920,
  pages		= {1--27},
  abstract	= {We propose a novel approach for the medial axis
		  approximation of triangulated solids by using a polyhedral
		  unit ball $B$ instead of the standard Euclidean unit ball.
		  By this means, we compute the exact medial axis
		  $MA(\Omega)$ of a triangulated solid $\Omega$ with respect
		  to a piecewise linear (quasi-)metric $d_B$. The obtained
		  representation of $\Omega$ by the medial axis transform
		  $MAT(\Omega)$ allows for a convenient computation of the
		  trimmed offset of $\Omega$ with respect to $d_B$. All
		  calculations are performed within the field of rational
		  numbers, resulting in a robust and efficient implementation
		  of our approach. Adapting the properties of $B$ provides an
		  easy way to control the level of details captured by the
		  medial axis, making use of the implicit pruning at flat
		  boundary features.}
}

@InProceedings{aabekm-nesca-00,
  author	= {O. Aichholzer and F. Aurenhammer and B. Brandtstaetter 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},
  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. Brandtstaetter and
		  H. Krasser and C. Magele and M. Muehlmann 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{aackrtx-tin-96,
  author	= {O. Aichholzer and F. Aurenhammer and S.-W. Cheng and N.
		  Katoh and G. Rote and M. Taschwer and Y.-F. Xu},
  title		= {Triangulations intersect nicely},
  journal	= {Discrete \& Computational Geometry},
  year		= 1996,
  volume	= 16,
  pages		= {339--359},
  note		= {Special Issue. [SFB Report F003-030, TU Graz, Austria,
		  1995]},
  abstract	= {We show that there is a matching between the edges of any
		  two triangulations of a planar point set such that an edge
		  of one triangulation is matched either to the identical
		  edge in the other triangulation or to an edge that crosses
		  it. This theorem also holds for the triangles of the
		  triangulations and in general independence systems. As an
		  application, we give some lower bounds for the minimum
		  weight triangulation which can be computed in polynomial
		  time by matching and network flow techniques. We exhibit an
		  easy-to-recognize class of point sets for which the
		  minimum-weight triangulation coincides with the greedy
		  triangulation.}
}

@InProceedings{aaclmp-vddsd-97,
  author	= {O. Aichholzer and F. Aurenhammer and D.Z. Chen and D.T.
		  Lee and A. Mukhopadhyay and E. Papadopoulou},
  title		= {{V}oronoi diagrams for direction-sensitive distances
		  (communication)},
  booktitle	= {Proc. $13^{th}$ Ann. ACM Symp. Computational Geometry},
  pages		= {418--420},
  year		= 1997,
  address	= {Nice, France},
  note		= {[SFB Report F003-098, TU Graz, Austria, 1996]},
  abstract	= {On a tilted plane $T$ in three-space, direction-sensitive
		  distances are defined as the Euclidean distance plus a
		  multiple of the signed difference in height. These
		  direction-sensitive distances, called skew distances
		  generalize the Euclidean distance and may model realistic
		  environments more closely than the Euclidean distance.
		  Various Voronoi diagrams and related problems under this
		  kind of distances are investigated. A relationship to
		  convex distance functions and to Euclidean Voronoi diagrams
		  for planar circles is shown, and is exploited for a
		  geometric analysis and a plane-sweep construction of
		  Voronoi diagrams on $T$. Several optimal algorithms based
		  on the direction-sensitive distances on $T$ are presented.
		  For example, an output-sensitive algorithm is developed for
		  computing the skew distance Voronoi diagram with $n$ sites
		  on $T$, in $O(n \log h)$ time and $O(n)$ space, where $h$
		  is the number of sites which have non-empty Voronoi regions
		  ($1 \leq h \leq n$). $O(n \log n)$ time and $O(n)$ space
		  algorithms are also given for several other problems under
		  skew distances, including the all nearest neighbors and the
		  layers of Voronoi diagram. These algorithms have certain
		  features different from their 'ordinary' counterparts based
		  on the Euclidean distance.}
}

@Article{aaclp-svd-99,
  author	= {O. Aichholzer and F. Aurenhammer and D.Z. Chen and D.T.
		  Lee and E. Papadopoulou},
  title		= {Skew {V}oronoi diagrams},
  journal	= {Int'l. Journal of Computational Geometry \& Applications},
  year		= 1999,
  volume	= 9,
  pages		= {235--247},
  htmlnote	= {Click here for <A
		  HREF="http://www.igi.TUgraz.at/oaich/skewvd/Welcome.html">Figures
		  and Animations</A> of Skew Voronoi Diagrams},
  abstract	= {On a tilted plane $T$ in three-space, {\em skew
		  distances\/} are defined as the Euclidean distance plus a
		  multiple of the signed difference in height. Skew distances
		  may model realistic environ\-ments more closely than the
		  Euclidean distance. Voro\-noi diagrams and related problems
		  under this kind of distances are investigated. A
		  relationship to convex distance functions and to Euclidean
		  Voronoi diagrams for planar circles is shown, and is
		  exploited for a geometric analysis and a plane-sweep
		  construction of Voronoi diagrams on $T$. An
		  output-sensitive algorithm running in time $O(n \log h)$ is
		  developed, where $n$ and $h$ is the number of sites and
		  non-empty Voronoi regions, respectively. The all nearest
		  neighbors problem for skew distances, which has certain
		  features different from its Euclidean counterpart, is
		  solved in $O(n \log n)$ time.}
}

@Article{aadhru-okcp-11,
  author	= {O. Aichholzer and F. Aurenhammer and E.D. Demaine and F.
		  Hurtado and P. Ramos and J. Urrutia},
  title		= {On $k$-convex polygons},
  journal	= {Computational Geometry: Theory and Applications},
  year		= 2012,
  volume	= 45,
  pages		= {73--87},
  abstract	= {We introduce the notion of $k$-convexity and explore
		  polygons in the plane that have this property. Polygons
		  which are $k$-convex can be triangulated with fast yet
		  simple algorithms. However, recognizing them is a 3SUM-hard
		  problem. We give a characterization of 2-convex polygons, a
		  particularly interesting class, and show how to recognize
		  them in $O(n \log n)$ time. A description of their shape is
		  given as well, which leads to Erd\"os-Szekeres type results
		  regarding subconfigurations of their vertex sets. Finally,
		  we introduce the concept of generalized geometric
		  permutations, and show that their number can be exponential
		  in the number of 2-convex objects considered.}
}

@InProceedings{aadhtv-09,
  author	= {O. Aichholzer and F. Aurenhammer and O. Devillers and T.
		  Hackl and M. Teillaud and B. Vogtenhuber},
  title		= {Lower and upper bounds on the number of empty cylinders
		  and ellipsoids},
  booktitle	= {Proc. $25^{th}$ European Workshop on Computational
		  Geometry EuroCG'09},
  address	= {Brussels, Belgium},
  pages		= {139--141},
  year		= 2009
}

@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.}
}

@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{aah-eoncs-00,
  author	= {O. Aichholzer and F. Aurenhammer and F. Hurtado},
  title		= {Edge Operations on Non-Crossing Spanning Trees},
  booktitle	= {Proc. $16^{th}$ European Workshop on Computational
		  Geometry CG '2000},
  pages		= {121--125},
  year		= 2000,
  address	= {Eilat, Israel},
  htmlnote	= {You can download our <A
		  HREF="http://www.igi.TUgraz.at/oaich/trees/Welcome.html">MST-Tool</A>.}
		  ,
  abstract	= {Let $S$ be a set of $n$ points in the Euclidean plane.
		  Consider the set ${\cal T}_S$ of all non-crossing spanning
		  trees of $S$. A {\em tree graph\/} ${\cal TG}_{\tt op}(S)$
		  is the graph that has ${\cal T}_S$ as its vertex set and
		  that connects vertex (tree) $T$ to vertex $T'$ iff $T' =
		  {\tt op}(T)$, where ${\tt op}$ is some operation that
		  exchanges two tree edges following a specific rule. The
		  existence of a path between two vertices in ${\cal TG}_{\tt
		  op}(S)$ means transformability of the corresponding trees
		  into each other by repeated application of the operation
		  ${\tt op}$. The length of a shortest path corresponds to
		  the distance between the two trees with respect to the
		  operation ${\tt op}$. Distances of this kind provide a
		  measure of similarity between trees. We prove new results
		  on ${\cal TG}_{\tt op}(S)$ for two classical operations
		  ${\tt op}$, namely the (improving and crossing-free) {\em
		  edge move\/} and the (crossing-free) {\em edge slide\/}.
		  Applications to morphing of trees and to the continuous
		  deformation of sets of line segments seem reasonable. Our
		  results mainly rely on a fact of interest in its own right:
		  Let $MST(S)$ and $DT(S)$ be the minimum spanning tree and
		  the Delaunay triangulation of $S$, respectively. Then any
		  pair $(T,\Delta)$, for $T \in {\cal T}_S$ and $\Delta$
		  being $T's$ constrained Delaunay triangulation, can be
		  transformed into the pair $(MST(S),DT(S))$ via a canonical
		  tree/triangulation sequence.}
}

@Article{aah-nrms-99,
  author	= {O. Aichholzer and F. Aurenhammer and R. Hainz},
  title		= {New results on {MWT} subgraphs},
  journal	= {Information Processing Letters},
  year		= 1999,
  volume	= 69,
  pages		= {215--219},
  note		= {[SFB Report F003-140, TU Graz, Austria, 1998]},
  abstract	= {Let $P$ be a polygon in the plane. We disprove the
		  conjecture that the so-called LMT-skeleton coincides with
		  the intersection of all locally minimal triangulations,
		  $LMT(P)$, even for convex polygons $P$. We introduce an
		  improved LMT-skeleton algorithm which, for any simple
		  polygon $P$, exactly computes $LMT(P)$, and thus a larger
		  subgraph of the minimum-weight triangulation $MWT(P)$. The
		  algorithm achieves the same in the general point set case
		  provided the connectedness of the improved LMT-skeleton,
		  which is given in allmost all practical instances. We
		  further observe that the $\beta$-skeleton of $P$ is a
		  subset of $MWT(P)$ for all values $\beta >
		  \sqrt{\frac{4}{3}}$ provided $P$ is convex or near-convex.
		  This gives evidence for the tightness of this bound in the
		  general point set case.}
}

@InProceedings{aah-ptlc-06,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl},
  title		= {Pre-triangulations and liftable complexes},
  booktitle	= {$22^{nd}$ Ann. ACM Symp. Computational Geometry},
  year		= 2006,
  pages		= {282--291},
  address	= {Sedona, Arizona, USA},
  abstract	= {We introduce and discuss the concept of
		  pre-triangulations, a relaxation of triangulations that
		  goes beyond the well-established class of
		  pseudo-triangulations.}
}

@Article{aah-ptlc-07,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl},
  title		= {Pre-triangulations and liftable complexes},
  journal	= {Discrete \& Computational Geometry},
  volume	= 38,
  year		= 2007,
  pages		= {701--725},
  abstract	= {We introduce the concept of pre-triangulations, a
		  relaxation of triangulations that goes beyond the
		  frequently used concept of pseudo-triangulations.
		  Pre-triangulations turn out to be more natural than
		  pseudo-triangulations in certain cases. We show that
		  pre-triangulations arise in three different contexts: In
		  the characterization of polygonal complexes that are
		  liftable to three-space in a strong sense, in flip
		  sequences for general polygonal complexes, and as graphs of
		  maximal locally convex functions.}
}

@Article{aah-sstft-00,
  author	= {O. Aichholzer and F. Aurenhammer and F. Hurtado},
  title		= {Sequences of spanning trees and a fixed tree theorem},
  year		= 2002,
  journal	= {Computational Geometry: Theory and Applications},
  volume	= {21},
  number	= {1--2},
  pages		= {3--20},
  note		= {Special Issue. [Report MA2-IR-00-00026, Universitat
		  Polite\'cnica de Catalunya, Barcelona, Spain, 2000]},
  htmlnote	= {You can also download the nice program <A
		  HREF="http://www.igi.TUGraz.at/oaich/trees/Welcome.html">MST-Tool</A>
		  we used to check and visualize some of the presented
		  results!},
  abstract	= {Let ${\cal T}_S$ be the set of all crossing-free spanning
		  trees of a planar $n$-point set $S$. We prove that ${\cal
		  T}_S$ contains, for each of its members $T$, a
		  length-decreasing sequence of trees $T_o,\ldots,T_k$ such
		  that $T_o=T$, $T_k=MST(S)$, $T_i$ does not cross $T_{i-1}$
		  for $i=1,\ldots,k$, and $k=O(\log n)$. Here $MST(S)$
		  denotes the Euclidean minimum spanning tree of the point
		  set $S$. As an implication, the number of length-improving
		  and planar edge moves needed to transform a tree $T \in
		  {\cal T}_S$ into $MST(S)$ is only $O(n\log n)$. Moreover,
		  it is possible to transform any two trees in ${\cal T}_S$
		  into each other by means of a local and constant-size edge
		  slide operation. Applications of these results to morphing
		  of simple polygons are possible by using a crossing-free
		  spanning tree as a skeleton description of a polygon.}
}

@Article{aahh-ccps-06,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and C.
		  Huemer},
  title		= {Connecting colored point sets},
  journal	= {Discrete Applied Mathematics},
  volume	= 155,
  year		= 2007,
  pages		= {271--278},
  abstract	= {We study the following Ramsey-type problem. Let \mbox{$S =
		  B \cup R$} be a two-colored set of $n$ points in the plane.
		  We show how to construct, in \mbox{$O(n \log n)$} time, a
		  crossing-free spanning tree $T(R)$ for~$R$, and a
		  crossing-free spanning tree $T(B)$ for~$B$, such that both
		  the number of crossings between $T(R)$ and $T(B)$ and the
		  diameters of~$T(R)$ and $T(B)$ are kept small. The
		  algorithm is conceptually simple and is implementable
		  without using any non-trivial data structure. This improves
		  over a previous method in Tokunaga~\cite{T} that is less
		  efficient in implementation and does not guarantee a
		  diameter bound.}
}

@InProceedings{aahhpv-3cpt,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and C.
		  Huemer and A. Pilz and B. Vogtenhuber},
  title		= {3-colorability of pseudo-triangulations},
  booktitle	= {Proc. $26^{th}$ European Workshop on Computational
		  Geometry EuroCG'10},
  address	= {Dortmund, Germany},
  pages		= {21--24},
  year		= 2010,
  abstract	= {Deciding $3$-colorability for general plane graphs is
		  known to be an NP-complete problem. However, for certain
		  classes of plane graphs, like triangulations, polynomial
		  time algorithms exist. We consider the family of
		  pseudo-triangulations (a generalization of triangulations)
		  and prove NP-completeness for this class, even if the
		  maximum face-degree is bounded to four, or pointed
		  pseudo-triangulations with maximum face degree five are
		  considered. As a complementary result, we show that for
		  pointed pseudo-triangulations with maximum face-degree
		  four, a $3$-coloring always exists and can be found in
		  linear time.}
}

@InProceedings{aahjos-csacbr-07,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Juettler and M. Oberneder and Z. Sir},
  title		= {Computational and Structural Advantages of Circular
		  Boundary Representation},
  booktitle	= {Proc. 10th Int. Workshop on Algorithms and Data
		  Structures, WADS'07, Springer LNCS 4619},
  year		= 2007,
  address	= {Halifax, Canada},
  pages		= {374-385},
  abstract	= {Boundary approximation of planar shapes by circular arcs
		  has quantitive and qualitative advantages compared to using
		  straight-line segments. We demonstrate this by way of three
		  basic and frequent computations on shapes -- convex hull,
		  decomposition, and medial axis. In particular, we propose a
		  novel medial axis algorithm that beats existing methods in
		  simplicity and practicality, and at the same time
		  guarantees convergence to the medial axis of the original
		  shape. }
}

@Article{aahjos-csacbr-10,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Juettler and M. Oberneder and Z. Sir},
  title		= {Computational and Structural Advantages of Circular
		  Boundary Representation},
  journal	= {Int'l Journal of Computational Geometry \& Applications},
  volume	= 21,
  year		= 2011,
  pages		= {47--69},
  abstract	= {Boundary approximation of planar shapes by circular arcs
		  has quantitive and qualitative advantages compared to using
		  straight-line segments. We demonstrate this by way of three
		  basic and frequent computations on shapes -- convex hull,
		  decomposition, and medial axis. In particular, we propose a
		  novel medial axis algorithm that beats existing methods in
		  simplicity and practicality, and at the same time
		  guarantees convergence to the medial axis of the original
		  shape.}
}

@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{aahkpp-abtob-07,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Kornberger and M. Peternell and H. Pottmann},
  title		= {Approximating boundary-triangulated objects with balls},
  booktitle	= {Proc. 23rd European Workshop on Computational Geometry,
		  EWCG'07},
  year		= 2007,
  address	= {Graz, Austria},
  pages		= {130--133},
  abstract	= {We compute a set of balls that approximates a given 3D
		  object, and we derive small additive bounds for the
		  overhead in balls with respect to the minimal solution with
		  the same quality. The algorithm has been implemented and
		  tested using the CGAL library.}
}

@InProceedings{aahkprsv-spia-08,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Kornberger and S. Plantinga and G. Rote and A. Sturm and G.
		  Vegter},
  title		= {Seed polytopes for incremental approximation},
  booktitle	= {Proc. $24^{th}$ European Workshop on Computational
		  Geometry EuroCG '08},
  year		= 2008,
  pages		= {13--16},
  address	= {Nancy, France},
  abstract	= {Approximating a three-dimensional object in order to
		  simplify its handling is a classical topic in computational
		  geometry and related fields. A typical approach is based on
		  incremental approximation algorithms, which start with a
		  small and topologically correct polytope representation
		  (the seed polytope) of a given sample point cloud or input
		  mesh. In addition, a correspondence between the faces of
		  the polytope and the respective regions of the object
		  boundary is needed to guarantee correctness.
		  
		  We construct such a polytope by first computing a
		  simplified though still homotopy equivalent medial axis
		  transform of the input object. Then, we inflate this medial
		  axis to a polytope of small size. Since our approximation
		  maintains topology, the simplified medial axis transform is
		  also useful for skin surfaces and envelope surfaces.}
}

@InProceedings{aahlrss-swe-05,
  author	= {B. Aronov and F. Aurenhammer and F. Hurtado and S.
		  Langerman and D. Rappaport and S. Smorodinsky and C.
		  Seara},
  title		= {Small weak epsilon nets},
  booktitle	= {Proc. $17^{th}$ Canadian Conference on Computational
		  Geometry CCCG '05},
  pages		= {51--54},
  year		= 2005,
  address	= {Windsor, Ontario},
  abstract	= {Let S be a family of sets in the plane. Let 0 <
		  epsilon(S,i) < 1 denote the minimum real number such that
		  for any finite point set P there exists a set Q of i points
		  that is a weak epsilon(S,i)-net for P with respect to S. We
		  derice upper and lower bounds on epsilon(S,i) for small
		  integers i and when S is the family of all convex sets, or
		  the family of all axis-parallel rectangles.}
}

@Article{aahlrss-swe-07,
  author	= {B. Aronov and F. Aurenhammer and F. Hurtado and S.
		  Langerman and D. Rappaport and S. Smorodinsky and C.
		  Seara},
  title		= {Small weak epsilon nets},
  journal	= {Computational Geometry: Theory and Applications},
  year		= 2009,
  volume	= 42,
  pages		= {455--462},
  note		= {Special Issue},
  abstract	= {Let S be a family of sets in the plane. Let 0 <
		  epsilon(S,i) < 1 denote the minimum real number such that
		  for any finite point set P there exists a set Q of i points
		  that is a weak epsilon(S,i)-net for P with respect to S. We
		  derice upper and lower bounds on epsilon(S,i) for small
		  integers i and when S is the family of all convex sets, or
		  the family of all axis-parallel rectangles.}
}

@InProceedings{aahru-tcp-09,
  author	= {O. Aichholzer and F. Aurenhammer and F. Hurtado and P.A.
		  Ramos and J. Urrutia},
  title		= {Two-convex polygons},
  booktitle	= {Proc. $25^{th}$ European Workshop on Computational
		  Geometry EuroCG'09},
  address	= {Brussels, Belgium},
  pages		= {117--120},
  year		= 2009,
  abstract	= {We introduce a notion of k-convexity and explore some
		  properties of polygons that have this property. In
		  particular, 2-convex polygons can be recognized in
		  \mbox{$O(n \log n)$} time, and k-convex polygons can be
		  triangulated in $O(kn)$ time.}
}

@Article{aahs-mwpt-08,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Speckmann},
  title		= {On minimum weight pseudo-triangulations},
  journal	= {Computational Geometry: Theory and Applications},
  year		= 2009,
  volume	= 42,
  pages		= {627--631},
  abstract	= {In this note we discuss some structural properties of
		  minimum weight pseudo-triangulations.}
}

@InProceedings{aahs-pmwpt-07,
  author	= {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
		  Speckmann},
  title		= {On (pointed) minimum weight pseudo-triangulations},
  booktitle	= {Proc. $19^{th}$ Canadian Conference on Computational
		  Geometry CCCG '07},
  year		= 2007,
  address	= {Ottawa, Canada},
  pages		= {209-212},
  abstract	= {In this note we discuss some structural properties of
		  minimum weight (pointed) pseudo-triangulations.}
}

@InProceedings{aahv-gcepslg-06,
  author	= {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
		  Vogtenhuber},
  title		= {Gray code enumeration of plane straight-line graphs},
  booktitle	= {Proc. $22^{nd}$ European Workshop on Computational
		  Geometry EuroCG '06},
  year		= 2006,
  pages		= {71--74},
  address	= {Delphi, Greece},
  abstract	= {We develop Gray code enumeration schemes for geometric
		  graphs in the plane. The considered graph classes include
		  plane straight-line graphs, plane spanning trees, and
		  connected plane straight-line graphs. Previous results were
		  restricted to the case where the underlying vertex set is
		  in convex position.}
}

@Article{aahv-gcepslg-07,
  author	= {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
		  Vogtenhuber},
  title		= {Gray code enumeration of plane straight-line graphs},
  journal	= {Graphs and Combinatorics},
  year		= 2007,
  volume	= 23,
  pages		= {467--479},
  abstract	= {We develop Gray code enumeration schemes for geometric
		  graphs in the plane. The considered graph classes include
		  plane straight-line graphs, plane spanning trees, and
		  connected plane straight-line graphs. Previous results were
		  restricted to the case where the underlying vertex set is
		  in convex position.}
}

@InProceedings{aaiklr-gsac-98a,
  author	= {O. Aichholzer and F. Aurenhammer and C. Icking and R.
		  Klein and E. Langetepe and G. Rote},
  title		= {Generalized self-approaching curves},
  booktitle	= {Proc. $14^{th}$ European Workshop on Computational
		  Geometry CG '98},
  pages		= {15--18},
  year		= 1998,
  address	= {Barcelona, Spain},
  abstract	= {We consider all planar oriented curves that have the
		  following property. For each point $B$ on the curve, the
		  rest of the curve lies inside a wedge of angle $\varphi$
		  with apex in $B$, where $\varphi < \Pi$ is fixed. This
		  property restrains the curve's meandering. we provide an
		  upper bound $c(\varphi)$ for the length of such a curve,
		  divided by the distance between its endpoints, and prove
		  this bound to be tight. A main step is in proving that the
		  curve's length cannot exceed the perimeter of its convex
		  hull, divided by $1+\cos(\varphi)$.}
}

@InProceedings{aaiklr-gsac-98b,
  author	= {O. Aichholzer and F. Aurenhammer and C. Icking and R.
		  Klein and E. Langetepe and G. Rote},
  title		= {Generalized self-approaching curves},
  booktitle	= {Proc. $9^{th}$ Int. Symp. Algorithms and Computation
		  ISAAC'98, Lecture Notes in Computer Science},
  pages		= {317--326},
  year		= 1998,
  volume	= 1533,
  address	= {Taejon, Korea},
  publisher	= {Springer Verlag},
  abstract	= {We consider all planar oriented curves that have the
		  following property depending on a fixed angle $\varphi$.
		  For each point $B$ on the curve, the rest of the curve lies
		  inside a wedge of angle $\varphi$ with apex in $B$. This
		  property restrains the curve's meandering, and for $\varphi
		  \leq \Pi/2$ this means that a point running along the curve
		  always gets closer to all points on the remaining part. For
		  all $\varphi < \Pi$, we provide an upper bound $c(\varphi)$
		  for the length of such a curve, divided by the distance
		  between its endpoints, and prove this bound to be tight. A
		  main step is in proving that the curve's length cannot
		  exceed the perimeter of its convex hull, divided by
		  $1+\cos(\varphi)$.}
}

@Article{aaiklr-vsac-00,
  author	= {O. Aichholzer and F. Aurenhammer and C. Icking and R.
		  Klein and E. Langetepe and G. Rote},
  title		= {Generalized self-approaching curves},
  journal	= {Discrete Applied Mathematics},
  year		= 2001,
  note		= {Special Issue. [SFB-Report F003-134, TU Graz, Austria,
		  1998]},
  pages		= {3--24},
  volume	= {109},
  number	= {1-2},
  abstract	= {We consider all planar oriented curves that have the
		  following property depending on a fixed angle $\varphi$.
		  For each point $B$ on the curve, the rest of the curve lies
		  inside a wedge of angle $\varphi$ with apex in $B$. This
		  property restrains the curve's meandering, and for $\varphi
		  \leq \Pi/2$ this means that a point running along the curve
		  always gets closer to all points on the remaining part. For
		  all $\varphi < \Pi$, we provide an upper bound $c(\varphi)$
		  for the length of such a curve, divided by the distance
		  between its endpoints, and prove this bound to be tight. A
		  main step is in proving that the curve's length cannot
		  exceed the perimeter of its convex hull, divided by
		  $1+\cos(\varphi)$.}
}

@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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/crossing.html">crossing
		  number homepage</A>.},
  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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/crossing.html">crossing
		  number homepage</A>.},
  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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/crossing.html">crossing
		  number homepage</A>.},
  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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/ordertypes.html">order
		  type homepage</A>.},
  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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/ordertypes.html">order
		  type homepage</A>.},
  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 <A
		  HREF="http://www.igi.TUgraz.at/oaich/triangulations/crossing.html">crossing
		  number homepage</A>.}
}

@InProceedings{aakprsv-rsro-09,
  author	= {O. Aichholzer and F. Aurenhammer and B. Kornberger and S.
		  Plantinga and G. Rote and A. Sturm and G. Vegter},
  title		= {Recovering structure from $r$-sampled objects},
  booktitle	= {Eurographics Symposium on Geometry Processing, Computer
		  Graphics Forum},
  volume	= {28},
  year		= 2009,
  address	= {Berlin, Germany},
  pages		= {1349-1360},
  note		= {Special Issue}
}

@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{aap-qpssc-02,
  author	= {O. Aichholzer and F. Aurenhammer and B. Palop},
  title		= {Quickest Paths, Straight Skeletons, and the City {V}oronoi
		  Diagram},
  year		= 2002,
  booktitle	= {Proc. $18^{th}$ Ann. ACM Symp. Computational Geometry},
  pages		= {151--159},
  address	= {Barcelona, Spain},
  abstract	= {The city Voronoi diagram is induced by quickest paths, in
		  the $L_1$~plane speeded up by an isothetic transportation
		  network. We investigate the rich geometric and algorithmic
		  properties of city Voronoi diagrams, and report on their
		  use in processing quickest-path queries.\\ In doing so, we
		  revisit the fact that not every Voronoi-type diagram has
		  interpretations in both the distance model and the
		  wavefront model. Especially, straight skeletons are a
		  relevant example where an interpretation in the former
		  model is lacking. We clarify the relation between these
		  models, and further draw a connection to the
		  bisector-defined abstract Voronoi diagram model, with the
		  particular goal of computing the city Voronoi diagram
		  efficiently. }
}

@Article{aap-qpssc-03,
  author	= {O. Aichholzer and F. Aurenhammer and B. Palop},
  title		= {Quickest Paths, Straight Skeletons, and the City {V}oronoi
		  Diagram},
  journal	= {Discrete \& Computational Geometry},
  volume	= 31,
  number	= 1,
  pages		= {17--35},
  year		= {2004},
  abstract	= {The city Voronoi diagram is induced by quickest paths, in
		  the $L_1$~plane speeded up by an isothetic transportation
		  network. We investigate the rich geometric and algorithmic
		  properties of city Voronoi diagrams, and report on their
		  use in processing quickest-path queries.\\ In doing so, we
		  revisit the fact that not every Voronoi-type diagram has
		  interpretations in both the distance model and the
		  wavefront model. Especially, straight skeletons are a
		  relevant example where an interpretation in the former
		  model is lacking. We clarify the relation between these
		  models, and further draw a connection to the
		  bisector-defined abstract Voronoi diagram model, with the
		  particular goal of computing the city Voronoi diagram
		  efficiently. }
}

@TechReport{aar-ogosa-95,
  author	= {O. Aichholzer and F. Aurenhammer and G. Rote},
  title		= {Optimal graph orientation with storage applications},
  institution	= {SFB 'Optimierung und Kontrolle', TU Graz, Austria},
  year		= 1995,
  type		= {SFB-Report},
  number	= {F003-51},
  abstract	= {We show that the edges of a graph with maximum edge
		  density $d$ can always be oriented such that each vertex
		  has in-degree at most $d$. Hence, for arbitrary graphs,
		  edges can always be assigned to incident vertices as
		  uniformly as possible. For example, in-degree 3 is achieved
		  for planar graphs. This immediately gives a space-optimal
		  data structure that answers edge membership queries in a
		  maximum edge density-$d$ graph in $O(\log d)$ time.}
}

@InProceedings{aart-tin-95,
  author	= {O. Aichholzer and F. Aurenhammer and G. Rote and M.
		  Taschwer},
  title		= {Triangulations intersect nicely},
  booktitle	= {Proc. $11^{th}$ Ann. ACM Symp. Computational Geometry},
  pages		= {220--229},
  year		= 1995,
  address	= {Vancouver, Canada},
  abstract	= {We prove that two different triangulations of the same
		  planar point set always intersect in a systematic manner,
		  concerning both their edges and their triangles. As a
		  consequence, improved lower bounds on the weight of a
		  triangulation are obtained by solving an assignment
		  problem. The new bounds cover the previously known bounds
		  and can be computed in polynomial time. As a by-product, an
		  easy-to-recognize class of point sets is exhibited where
		  the minimum-weight triangulation coincides with the greedy
		  triangulation.}
}

@InProceedings{aarx-clgta-96,
  author	= {O. Aichholzer and F. Aurenhammer and G. Rote and Y.-F.
		  Xu},
  title		= {Constant-level greedy triangulations approximate the {MWT}
		  well},
  booktitle	= {Proc. $2^{nd}$ Int'l. Symp. Operations Research \&
		  Applications ISORA'96, Lecture Notes in Operations
		  Research},
  pages		= {309--318},
  year		= 1996,
  editor	= {Du, Zhang, Cheng},
  volume	= 2,
  address	= {Guilin, P. R. China},
  publisher	= {World Publishing Corporation},
  abstract	= {The well-known greedy triangulation $GT(S)$ of a finite
		  point set $S$ is obtained by inserting compatible edges in
		  increasing length order, where an edge is compatible if it
		  does not cross previously inserted ones. Exploiting the
		  concept of so-called light edges, we introduce a definition
		  of $GT(S)$ that does not rely on the length ordering of the
		  edges. Rather, it provides a decomposition of $GT(S)$ into
		  levels, and the number of levels allows us to bound the
		  total edge length of $GT(S)$. In particular, we show
		  $|GT(S)| \leq 3 \cdot 2^{k+1} |MWT(S)|$, where $k$ is the
		  number of levels and $MWT(S)$ is the minimum-weight
		  triangulation of $S$.}
}

@Article{aarx-clgta-99,
  author	= {O. Aichholzer and F. Aurenhammer and G. Rote and Y.-F.
		  Xu},
  title		= {Constant-level greedy triangulations approximate the {MWT}
		  well},
  journal	= {Journal of Combinatorial Optimization},
  year		= 1999,
  volume	= 2,
  pages		= {361--369},
  note		= {[SFB-Report F003-050, TU Graz, Austria, 1995]},
  abstract	= {The well-known greedy triangulation $GT(S)$ of a finite
		  point set $S$ is obtained by inserting compatible edges in
		  increasing length order, where an edge is compatible if it
		  does not cross previously inserted ones. Exploiting the
		  concept of so-called light edges, we introduce a definition
		  of $GT(S)$ that does not rely on the length ordering of the
		  edges. Rather, it provides a decomposition of $GT(S)$ into
		  levels, and the number of levels allows us to bound the
		  total edge length of $GT(S)$. In particular, we show
		  $|GT(S)| \leq 3 \cdot 2^{k+1} |MWT(S)|$, where $k$ is the
		  number of levels and $MWT(S)$ is the minimum-weight
		  triangulation of $S$.}
}

@InProceedings{aarx-ngta-96,
  author	= {O. Aichholzer and F. Aurenhammer and G. Rote and Y.-F.
		  Xu},
  title		= {New greedy triangulation algorithms},
  booktitle	= {Proc. $12^{th}$ European Workshop on Computational
		  Geometry CG '96},
  pages		= {11--14},
  year		= 1996,
  address	= {Muenster, Germany},
  abstract	= {The classical greedy triangulation (GT) of a set $S$ of
		  $n$ points in the plane is the triangulation obtained by
		  starting with the empty set (of edges) and at each step
		  adding the shortest compatible edge between two of the
		  points of $S$, where a compatible edge is defined to be an
		  edge that crosses none of the previously added edges. In
		  this paper we use the greedy method as a general concept to
		  compute a triangulation of a planar point set. We use
		  either edges or triangles as basic objects. Furthermore we
		  give different variants to compute the weight of the
		  objects, either in a static or dynamic way, leading to a
		  total of $156$ different greedy triangulation algorithms.
		  We investigate these algorithms in their quality of
		  approximating the MWT.}
}

@Article{aaw-afa-02,
  author	= {O. Aichholzer and F. Aurenhammer and T. Werner},
  title		= {Algorithmic Fun - {A}balone},
  journal	= {Special Issue on Foundations of Information Processing of
		  {TELEMATIK}},
  pages		= {4--6},
  year		= {2002},
  volume	= 1,
  address	= {Graz, Austria}
}

@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{ads-ccq-08,
  author	= {F. Aurenhammer and M. Demuth and T. Schiffer},
  title		= {Computing convex quadrangulations},
  booktitle	= {Proc. 5th Ann. Int. Symp. Voronoi Diagrams in Science and
		  Engineering, Voronoi's Impact on Modern Science},
  year		= 2008,
  address	= {Kiev, Ukraine},
  volume	= 4,
  pages		= {32--43},
  abstract	= {We use projected Delaunay tetrahedra and a maximum
		  independent set approach to compute large subsets of convex
		  quadrangulations on a given set of points in the plane. The
		  new method improves over the popular pairing method based
		  on triangulating the point set.}
}

@Article{sad-ccq-11,
  author	= {T. Schiffer and F. Aurenhammer and M. Demuth},
  title		= {Computing convex quadrangulations},
  journal	= {Discrete Applied Mathematics},
  year		= 2012,
  volume	= {160},
  pages		= {648--656},
  abstract	= {We use projected Delaunay tetrahedra and a maximum
		  independent set approach to compute large subsets of convex
		  quadrangulations on a given set of points in the plane. The
		  new method improves over the popular pairing method based
		  on triangulating the point set.}
}

@Article{ae-oacwv-84,
  author	= {F. Aurenhammer and H. Edelsbrunner},
  title		= {An optimal algorithm for constructing the weighted
		  {V}oronoi diagram in the plane},
  journal	= {Pattern Recognition},
  year		= 1984,
  volume	= 17,
  number	= 2,
  pages		= {251--257},
  note		= {[IIG-Report-Series F109, TU Graz, Austria, 1983]},
  abstract	= {Let $S$ denote a set of $n$ points in the plane such that
		  each point $p$ has assigned a positive weight $w(p)$ which
		  expresses its capability to influence its neighborhood. In
		  this sense, the weighted distance of an arbitrary point $x$
		  from $p$ is gived by $d_e(x,p)/w(p)$, where $d_e$ denotes
		  the Euclidean distance function. The weighted Voronoi
		  diagram for $S$ is a subdivision of the plane such that
		  each point $p$ in $S$ is associated with a region
		  consisting of all points $x$ in the plane for which $p$ is
		  a weighted nearest point of $S$. An algorithm which
		  constructs the weighted Voronoi diagram for $S$ in $O(n^2)$
		  time is outlined in this paper. The method is optimal as
		  the diagram can consist of $\Theta(n^2)$ faces, edges, and
		  vertices.}
}

@Article{afisw-fiepc-94,
  author	= {F. Aurenhammer and M. Formann and R. Idury and A.
		  Schaeffer and F. Wagner},
  title		= {Faster isometric embedding in products of complete
		  graphs},
  journal	= {Discrete Applied Mathematics},
  year		= 1994,
  volume	= 52,
  pages		= {17--28},
  note		= {[Report B-90-06, FU Berlin, Germany, 1990]},
  abstract	= {An isometric embedding of a connected graph $G$ into a
		  cartesian product of complete graphs is equivalent to a
		  labeling of each vertex of $G$ by a string of fixed length
		  such that the distance in $G$ between two vertices is equal
		  to the Hamming distance between their labels. We give a
		  simple $O(D(m,n)+n^{2})$-time algorithm for deciding if $G$
		  admits such an embedding, and for labeling $G$ if one
		  exists, where $D(m,n)$ is the time needed to compute the
		  all-pairs distance matrix of a graph with $m$ edges and $n$
		  vertices. If the distance matrix is part of the input, our
		  algorithm runs in $O(n^{2})$ time. We also show that an
		  $n$-vertex subgraph of $(K_{a})^{d}$, the cartesian product
		  of $d$ equal-sized complete graphs, cannot have more than
		  $\frac{a-1}{2}n\log_a n$ edges. With this result our
		  algorithm can be used to decide whether a graph $G$ is an
		  $a$-ary Hamming graph in $O(n^2\log n)$ time (for fixed
		  $a$).}
}

@InProceedings{ah-ceceg-89,
  author	= {F. Aurenhammer and J. Hagauer},
  title		= {Computing equivalence classes among the edges of a graph
		  with applications},
  booktitle	= {Proc. Int'l Conf. Algebraic Graph Theory},
  year		= 1989,
  pages		= {11},
  address	= {Leibnitz, Austria},
  abstract	= {For two edges $e=(x,y)$ and $e'=(x',y')$ of a connected
		  graph $G=(V,E)$ let $e \Theta e'$ iff $d(x,x') + d(y,y')
		  \neq d(x,y') + d(x',y)$. Here $d(x,y)$ denotes the length
		  of a shortest path in $G$ joining vertices $x$ and $y$. An
		  algorithm is presented that computes the equivalence
		  classes induced on $E$ by the transitive closure
		  $\hat{\Theta}$ of $\Theta$ in time $O(|V||E|)$ and space
		  $O(|V|^2)$. Finding the equivalence classes of
		  $\hat{\Theta}$ is the primary step of several graph algorithms.}
}

@Article{ah-ceceg-92,
  author	= {F. Aurenhammer and J. Hagauer},
  title		= {Computing equivalence classes among the edges of a graph
		  with applications},
  journal	= {Discrete Mathematics},
  year		= 1992,
  volume	= 109,
  pages		= {3--12},
  note		= {Special Issue. [IIG-Report-Series 271, TU Graz, Austria,
		  1989]},
  abstract	= {For two edges $e=(x,y)$ and $e'=(x',y')$ of a connected
		  graph $G=(V,E)$ let $e \Theta e'$ iff $d(x,x') + d(y,y')
		  \neq d(x,y') + d(x',y)$. Here $d(x,y)$ denotes the length
		  of a shortest path in $G$ joining vertices $x$ and $y$. An
		  algorithm is presented that computes the equivalence
		  classes induced on $E$ by the transitive closure
		  $\hat{\Theta}$ of $\Theta$ in time $O(|V||E|)$ and space
		  $O(|V|^2)$. Finding the equivalence classes of
		  $\hat{\Theta}$ is the primary step of several graph algorithms.}
}

@InProceedings{ah-rbhgo-91,
  author	= {F. Aurenhammer and J. Hagauer},
  title		= {Recognizing binary {H}amming graphs in {$O(n^{2} \log n)$}
		  time},
  booktitle	= {Proc. $16^{th}$ Int'l Workshop on Graph-Theoretical
		  Concepts in Computer Science, Lecture Notes in Computer
		  Science},
  pages		= {90--98},
  year		= 1991,
  volume	= 484,
  address	= {Berlin, Germany},
  publisher	= {Springer Verlag},
  abstract	= {A graph $G$ is called a binary Hamming graph if each
		  vertex of $G$ can be assigned a binary address of fixed
		  length such that the Hamming distance between two addresses
		  equals the length of a shortest path between the
		  corresponding vertices. It is shown that $O(n^2 \log n)$
		  time suffices for deciding whether a given $n$-vertex graph
		  $G$ is a binary Hamming graph, and for computing a valid
		  addressing scheme for $G$ provided its existence. This is
		  not far from being optimal as $n$ addresses of length $n-1$
		  have to be computed in the worst case.}
}

@Article{ah-rbhgo-95,
  author	= {F. Aurenhammer and J. Hagauer},
  title		= {Recognizing binary {H}amming graphs in {$O(n^{2} \log n)$}
		  time},
  journal	= {Mathematical Systems Theory},
  year		= 1995,
  volume	= 28,
  pages		= {387--395},
  note		= {[IIG-Report-Series 273, TU Graz, Austria, 1989]},
  abstract	= {A graph $G$ is called a binary Hamming graph if each
		  vertex of $G$ can be assigned a binary address of fixed
		  length such that the Hamming distance between two addresses
		  equals the length of a shortest path between the
		  corresponding vertices. It is shown that $O(n^2 \log n)$
		  time suffices for deciding whether a given $n$-vertex graph
		  $G$ is a binary Hamming graph, and for computing a valid
		  addressing scheme for $G$ provided its existence. This is
		  not far from being optimal as $n$ addresses of length $n-1$
		  have to be computed in the worst case.}
}

@InProceedings{aha-lsp-92,
  author	= {F. Aurenhammer and F. Hoffmann and B. Aronov},
  title		= {Least-squares partitioning},
  booktitle	= {Proc. $8^{th}$ European Workshop on Computational Geometry
		  CG '92},
  pages		= {55--57},
  year		= 1992,
  address	= {Utrecht, the Netherlands}
}

@InProceedings{aha-mttls-92,
  author	= {F. Aurenhammer and F. Hoffmann and B. Aronov},
  title		= {{M}inkowski-type theorems and least-squares partitioning},
  booktitle	= {Proc. $8^{th}$ Ann. ACM Symp. Computational Geometry},
  pages		= {350--357},
  year		= 1992,
  address	= {Berlin, Germany},
  note		= {[Report B-92-09, FU Berlin, Germany, 1992]},
  abstract	= {The power diagram of $n$ weighted sites partitions a given
		  $m$-point set into clusters, one cluster for each region of
		  the diagram. In this way, an assignment of points to sites
		  is induced. We show the equivalence of such assignments to
		  constrained Euclidean least-squares assignments. As a
		  corollary, there always exists a power diagram whose
		  regions partition a given $d$-dimensional $m$-point set
		  into clusters of prescribed sizes, no matter where the
		  sites are placed. Another consequence is that least-squares
		  assignments can be computed by finding suitable weights for
		  the sites. In the plane, this takes roughly $O(n^2m)$ time
		  and optimal space $O(m)$, which improves on previous
		  methods. We further show that a constrained least-squares
		  assignment can be computed by solving a particular linear
		  program in $n+1$ dimensions. This leads to an algorithm for
		  iteratively improving the weights. Aside from the obvious
		  application, least-squares assignments are shown to be
		  useful in solving a certain transportation problem, and in
		  finding least-squares fittings where translation and
		  scaling are allowed. Finally, we extend the concept of a
		  constrained least-squares assignment to continuous point
		  sets, thereby obtaining results on power diagrams with
		  prescribed region volumes that are related to Minkowski's
		  theorem for convex polytopes.}
}

@Article{aha-mttls-98,
  author	= {F. Aurenhammer and F. Hoffmann and B. Aronov},
  title		= {{M}inkowski-type theorems and least-squares clustering},
  journal	= {Algorithmica},
  year		= 1998,
  volume	= 20,
  pages		= {61--76},
  note		= {[SFB Report F003-075, TU Graz, Austria, 1996]},
  abstract	= {Dissecting Euclidean $d$-space with the power diagram of
		  $n$ weighted point sites partitions a given $m$-point set
		  into clusters, one cluster for each region of the diagram.
		  In this manner, an assignment of points to sites is
		  induced. We show the equivalence of such assignments to
		  constrained Euclidean least-squares assignments. As a
		  corollary, there always exists a power diagram whose
		  regions partition a given $d$-dimensional $m$-point set
		  into clusters of prescribed sizes, no matter where the
		  sites are placed. Another consequence is that constrained
		  least-squares assignments can be computed by finding
		  suitable weights for the sites. In the plane, this takes
		  roughly $O(n^2m)$ time and optimal space $O(m)$, which
		  improves on previous methods. We further show that a
		  constrained least-squares assignment can be computed by
		  solving a specially structured linear program in $n+1$
		  dimensions. This leads to an algorithm for iteratively
		  improving the weights, based on the gradient-descent
		  method. Besides having the obvious optimization property,
		  least-squares assignments are shown to be useful in solving
		  a certain transportation problem, and in finding a
		  least-squares fitting of two point sets where translation
		  and scaling are allowed. Finally, we extend the concept of
		  a constrained least-squares assignment to continuous
		  distributions of points, thereby obtaining existence
		  results for power diagrams with prescribed region volumes.
		  These results are related to Minkowski's theorem for convex
		  polytopes. The aforementioned iterative method for
		  approximating the desired power diagram applies to
		  continuous distributions as well.}
}

@Article{ahi-cgflc-92,
  author	= {F. Aurenhammer and J. Hagauer and W. Imrich},
  title		= {{C}artesian graph factorization at logarithmic cost per
		  edge},
  journal	= {Computational Complexity},
  year		= 1992,
  volume	= 2,
  pages		= {331--349},
  abstract	= {Let $G$ be a connected graph with $n$ vertices and $m$
		  edges. We develop an algorithm that finds the prime factors
		  of $G$ with respect to Cartesian multiplication in $O(m
		  \log n)$ time and $O(m)$ space. This shows that factoring
		  $G$ is at most as costly as sorting its edges. The
		  algorithm gains its efficiency and practicality from using
		  only basic properties of product graphs and simple data
		  structures.}
}

@InProceedings{ahi-fcpgl-90,
  author	= {F. Aurenhammer and J. Hagauer and W. Imrich},
  title		= {Factoring {C}artesian-product graphs at logarithmic cost
		  per edge},
  booktitle	= {Proc. MPS Conf. Integer Programming and Combinatorial
		  Optimization IPCO'90},
  pages		= {29--44},
  year		= 1990,
  address	= {Waterloo, Canada},
  note		= {[IIG-Report-Series 287, TU Graz, Austria, 1990]},
  abstract	= {Let $G$ be a connected graph with $n$ vertices and $m$
		  edges. We develop an algorithm that finds the prime factors
		  of $G$ with respect to Cartesian multiplication in $O(m
		  \log n)$ time and $O(m)$ space. This shows that factoring
		  $G$ is at most as costly as sorting its edges. The
		  algorithm gains its efficiency and practicality from using
		  only basic properties of product graphs and simple data
		  structures.}
}

@InProceedings{ai-gravd-87,
  author	= {F. Aurenhammer and H. Imai},
  title		= {Geometric relations among {V}oronoi diagrams},
  booktitle	= {Proc. $4^{th}$ Ann. STACS, Lecture Notes in Computer
		  Science},
  pages		= {53--65},
  year		= 1987,
  volume	= 247,
  address	= {Passau, Germany},
  publisher	= {Springer Verlag},
  abstract	= {Two general classes of Voronoi diagrams are introduced
		  and, along with their modifications to higher order, are
		  shown to be geometrically related. This geometric
		  background, on the one hand, serves to analyze the size and
		  the combinatorial structure, and on the other hand, implies
		  general and efficient methods of construction, for various
		  important types of Voronoi diagrams considered in the
		  literature.}
}

@Article{ai-grvd-88,
  author	= {F. Aurenhammer and H. Imai},
  title		= {Geometric relations among {V}oronoi diagrams},
  journal	= {Geometriae Dedicata},
  year		= 1988,
  volume	= 27,
  pages		= {65--75},
  note		= {[IIG-Report-Series 228, TU Graz, Austria, 1986]},
  abstract	= {Two general classes of Voronoi diagrams are introduced
		  and, along with their modifications to higher order, are
		  shown to be geometrically related. This geometric
		  background, on the one hand, serves to analyze the size and
		  the combinatorial structure, and on the other hand, implies
		  general and efficient methods of construction, for various
		  important types of Voronoi diagrams considered in the
		  literature.}
}

@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-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.}
}

@InCollection{ak-vd-00,
  author	= {F. Aurenhammer and R. Klein},
  title		= {{V}oronoi diagrams},
  booktitle	= {Handbook of Computational Geometry, Chapter V},
  pages		= {201--290},
  publisher	= {Elsevier Science Publishing},
  year		= 2000,
  editor	= {J. Sack and G. Urrutia},
  note		= {[SFB Report F003-092, TU Graz, Austria, 1996]},
  abstract	= {The topic of this chapter -- Voronoi diagrams -- differs
		  from other areas of computational geometry, in that its
		  origin dates back to the 17th century. In his book on the
		  principles of philosophy, R.~Descartes' illustrations show
		  a decomposition of space into convex regions, whose
		  underlying idea seems to be that of a Voronoi diagram. This
		  concept has independently emerged, and proven useful, in
		  various fields of science. Different names particular to
		  the respective field have been used, such as {\em medial
		  axis transform\/} in biology and physiology, {\em
		  Wigner-Seitz zones\/} in chemistry and physics, {\em
		  domains of action\/} in crystallography, and {\em Thiessen
		  polygons\/} in metereology and geography. The
		  mathematicians Dirichlet and Voronoi were the first to
		  formally introduce this concept. The resulting structure
		  has been called {\em Dirichlet tessellation\/} or {\em
		  Voronoi diagram\/}, which has become its standard name
		  today. Voronoi was the first to consider the {\em dual\/}
		  of this structure, where any two point sites are connected
		  whose regions have a boundary in common. Later, Delaunay
		  obtained the same by defining that two point sites are
		  connected if and only if they lie on a circle whose
		  interior contains no other point site. After him, the dual
		  of the Voronoi diagram has been denoted {\em Delaunay
		  tessellation\/} or {\em Delaunay triangulation\/}. Besides
		  its applications in other fields of science, the Voronoi
		  diagram and its dual can be used for solving numerous, and
		  surprisingly different, geometric problems. Moreover, these
		  structures are very appealing, and a lot of research has
		  been devoted to their study (about one out of 16 papers in
		  computational geometry), ever since Shamos and Hoey
		  introduced them to the field. Within one chapter, we cannot
		  review all known results and applications. Instead, we are
		  trying to highlight the intrinsic potential of Voronoi
		  diagrams, that lies in its structural properties, in the
		  existence of efficient algorithms for its construction, and
		  in its adaptability.}
}

@Article{akkox-autmp-00a,
  author	= {F. Aurenhammer and N. Katoh and H. Kojima and M. Ohsaki
		  and Y.-F. Xu},
  title		= {Approximating uniform triangular meshes in polygons},
  journal	= {Theoretical Computer Science},
  year		= 2002,
  volume	= 289,
  pages		= {879--895},
  note		= {Special Issue. [SFB Report F003-159, TU Graz, Austria,
		  1999]},
  abstract	= {We consider the problem of triangulating a convex polygon
		  using $n$ Steiner points under the following optimality
		  criteria: (1) minimizing the overall edge length ratio, (2)
		  minimizing the maximum edge length, and (3) minimizing the
		  maximum triangle perimeter. We establish a relation of
		  these problems to a certain extreme packing problem. Based
		  on this relationship, we develop a heuristic producing
		  constant approximations for all the optimality criteria
		  above (provided $n$ is chosen sufficiently large). That is,
		  the produced triangular mesh is {\em uniform} in these
		  respects. The method is easy to implement and runs in
		  $O(n^2 \log n)$ time and $O(n)$ space. The observed runtime
		  is much less. Moreover, for criterion (1) the method works
		  -- within the same complexity and approximation bounds --
		  for {\em arbitrary} polygons with possible holes, and for
		  criteria (2) and (3) it does so for a large subclass.}
}

@InProceedings{akkox-autmp-00b,
  author	= {F. Aurenhammer and N. Katoh and H. Kojima and M. Ohsaki
		  and Y.-F. Xu},
  title		= {Approximating uniform triangular meshes in polygons},
  booktitle	= {Proc. $6^{th}$ Ann. Intl. Computing and Combinatorics
		  Conference, Lecture Notes in Computer Science},
  pages		= {23--33},
  year		= 2000,
  volume	= {1558},
  address	= {Sydney, Australia},
  publisher	= {Springer Verlag},
  abstract	= {We consider the problem of triangulating a convex polygon
		  using $n$ Steiner points under the following optimality
		  criteria: (1) minimizing the overall edge length ratio, (2)
		  minimizing the maximum edge length, and (3) minimizing the
		  maximum triangle perimeter. We establish a relation of
		  these problems to a certain extreme packing problem. Based
		  on this relationship, we develop a heuristic producing
		  constant approximations for all the optimality criteria
		  above (provided $n$ is chosen sufficiently large). That is,
		  the produced triangular mesh is {\em uniform} in these
		  respects. The method is easy to implement and runs in
		  $O(n^2 \log n)$ time and $O(n)$ space. The observed runtime
		  is much less. Moreover, for criterion (1) the method works
		  -- within the same complexity and approximation bounds --
		  for {\em arbitrary} polygons with possible holes, and for
		  criteria (2) and (3) it does so for a large subclass.}
}

@InProceedings{appw-vdos-07,
  author	= {F. Aurenhammer and M. Peternell and H. Pottmann and J.
		  Wallner},
  title		= {Voronoi Diagrams for Oriented Spheres},
  booktitle	= {Proc. 4th Int. Symp. on Voronoi Diagrams in Science and
		  Engineering, ISVD'07},
  year		= 2007,
  pages		= {33--37},
  address	= {Pontypridd, UK},
  abstract	= {We consider finite sets of oriented spheres in (k-1)-space
		  and, by interpreting such spheres as points in k-space,
		  study the Voronoi diagrams they induce for several variants
		  of distance between spheres. We give bounds on the
		  combinatorial complexity of these diagrams in the plane and
		  in 3-space, and derive properties useful for constructing
		  them. Our results are motivated by applications to special
		  relativity theory.}
}

@InProceedings{as-fvd-90,
  author	= {F. Aurenhammer and G. Stoeckl},
  title		= {Fenster - {V}oronoi {D}iagramme ({A}bstract)},
  booktitle	= {Tagungsband DMV Jubilaeumstagung},
  pages		= 52,
  year		= 1990,
  address	= {Bremen, Germany},
  abstract	= {In the peeper's Voronoi diagram for $n$ sites, any point
		  in the plane belongs to the region of the closest site
		  visible from it. Visibility is constrained to a segment on
		  a line avoiding the convex hull of the sites. We show that
		  the peeper's Voronoi diagram attains a size of
		  $\Theta(n^{2})$ in the worst case, and that it can be
		  computed in $O(n^{2})$ time and space.}
}

@Article{as-pvd-91,
  author	= {F. Aurenhammer and G. Stoeckl},
  title		= {On the peeper's {V}oronoi diagram},
  journal	= {SIGACT News},
  year		= 1991,
  volume	= 22,
  number	= 4,
  pages		= {50--59},
  note		= {[IIG-Report-Series 264, TU Graz, Austria, 1988]},
  abstract	= {In the peeper's Voronoi diagram for $n$ sites, any point
		  in the plane belongs to the region of the closest site
		  visible from it. Visibility is constrained to a segment on
		  a line avoiding the convex hull of the sites. We show that
		  the peeper's Voronoi diagram attains a size of
		  $\Theta(n^{2})$ in the worst case, and that it can be
		  computed in $O(n^{2})$ time and space.}
}

@InProceedings{as-solri-91,
  author	= {F. Aurenhammer and O. Schwarzkopf},
  title		= {A simple on-line randomized incremental algorithm for
		  computing higher order {V}oronoi diagrams},
  booktitle	= {Proc. $7^{th}$ Ann. ACM Symp. Computational Geometry},
  pages		= {142--151},
  year		= 1991,
  address	= {North Conway, U.S.A.},
  abstract	= {We present a simple algorithm for maintaining order-$k$
		  Voronoi diagrams in the plane. By using a duality transform
		  that is of interest in its own right, we show that the
		  insertion or deletion of a site involves little more than
		  the construction of a single convex hull in three-space. In
		  particular, the order-$k$ Voronoi diagram for $n$ sites can
		  be computed in time $O(nk^{2} \log n + nk \log^{3} n)$ and
		  optimal space $O(k(n-k))$ by an on-line randomized
		  incremental algorithm. The time bound can be improved by a
		  logarithmic factor without losing much simplicity. For $k
		  \geq \log^{2} n$, this is optimal for a randomized
		  incremental construction; we show that the expected number
		  of structural changes during the construction is $\Theta
		  (nk^{2})$. Finally, by going back to primal space, we
		  obtain a dynamic data structure that supports $k$-nearest
		  neighbor queries, insertions, and deletions in a planar set
		  of sites. The structure promises easy implementation,
		  exhibits a satisfactory expected performance, and occupies
		  no more storage than the current order-$k$ Voronoi diagram.}
}

@Article{as-solri-92,
  author	= {F. Aurenhammer and O. Schwarzkopf},
  title		= {A simple on-line randomized incremental algorithm for
		  computing higher order {V}oronoi diagrams},
  journal	= {Int'l Journal of Computational Geometry \& Applications},
  year		= 1992,
  volume	= 2,
  pages		= {363--381},
  note		= {Special Issue. [Report B 91-02, FU Berlin, Germany,
		  1991]},
  abstract	= {We present a simple algorithm for maintaining order-$k$
		  Voronoi diagrams in the plane. By using a duality transform
		  that is of interest in its own right, we show that the
		  insertion or deletion of a site involves little more than
		  the construction of a single convex hull in three-space. In
		  particular, the order-$k$ Voronoi diagram for $n$ sites can
		  be computed in time $O(nk^{2} \log n + nk \log^{3} n)$ and
		  optimal space $O(k(n-k))$ by an on-line randomized
		  incremental algorithm. The time bound can be improved by a
		  logarithmic factor without losing much simplicity. For $k
		  \geq \log^{2} n$, this is optimal for a randomized
		  incremental construction; we show that the expected number
		  of structural changes during the construction is $\Theta
		  (nk^{2})$. Finally, by going back to primal space, we
		  obtain a dynamic data structure that supports $k$-nearest
		  neighbor queries, insertions, and deletions in a planar set
		  of sites. The structure promises easy implementation,
		  exhibits a satisfactory expected performance, and occupies
		  no more storage than the current order-$k$ Voronoi diagram.}
}

@InProceedings{as-sslro-92a,
  author	= {F. Aurenhammer and G. Stoeckl},
  title		= {Searching for segments with largest relative overlap},
  booktitle	= {Proc. $15^{th}$ IFIP Conf. System Modelling and
		  Optimization, Lecture Notes in Control and Information
		  Sciences},
  pages		= {77--84},
  year		= 1992,
  volume	= 180,
  address	= {Zuerich, Switzerland},
  publisher	= {Springer Verlag},
  abstract	= {Let $S$ be a set of $n$ possibly intersecting line
		  segments on the $x$-axis. A data structure is developed
		  that -- for an arbitrary query segment $\sigma$ -- reports
		  in $O(\log)$ time a segment in $S$ which yields the largest
		  relative overlap with $\sigma$. The structure needs $O(n
		  \log)$ time and $O(n)$ space for construction. These bounds
		  are asymptotically optimal.}
}

@Article{as-sslro-92b,
  author	= {F. Aurenhammer and G. Stoeckl},
  title		= {Searching for segments with largest relative overlap},
  journal	= {Information Processing Letters},
  year		= 1992,
  volume	= 41,
  pages		= {103--108},
  note		= {[Report B 91-10, FU Berlin, Germany, 1991]},
  abstract	= {Let $S$ be a set of $n$ possibly intersecting line
		  segments on the $x$-axis. A data structure is developed
		  that -- for an arbitrary query segment $\sigma$ -- reports
		  in $O(\log)$ time a segment in $S$ which yields the largest
		  relative overlap with $\sigma$. The structure needs $O(n
		  \log)$ time and $O(n)$ space for construction. These bounds
		  are asymptotically optimal.}
}

@InProceedings{asw-popfp-91,
  author	= {F. Aurenhammer and G. Stoeckl and E. Welzl},
  title		= {The post-office problem for fuzzy point sets},
  booktitle	= {Proc. $7^{th}$ Workshop on Computational Geometry CG '91,
		  Lecture Notes in Computer Science},
  pages		= {1--11},
  year		= 1991,
  volume	= 553,
  address	= {Bern, Switzerland},
  publisher	= {Springer Verlag},
  note		= {[Report B 91-07, FU Berlin, Germany, 1991]},
  abstract	= {The post-office problem for $n$ point sites in the plane
		  (determine which site is closest to a later specified query
		  point) is generalized to the situation when the residence
		  of each site is uncertain and it is described via uniform
		  distribution within a disk. Two probabilistic concepts of
		  neighborhood, -- expected closest site and probably closest
		  site -- are discussed and the resulting Voronoi diagrams
		  are investigated from a combinatorial and computational
		  point of view.}
}

@InCollection{ax-ot-07,
  author	= {F. Aurenhammer and Y.-F.Xu},
  title		= {Optimal triangulations},
  booktitle	= {Encyclopedia of Optimization, Second Edition},
  publisher	= {Springer},
  editor	= {C.A.Floudas, P.M.Pardalos},
  year		= 2008,
  pages		= {2757--2764},
  abstract	= {A {\em triangulation} of a given set $S$ of $n$ points in
		  the plane is a maximal set of non-crossing line segments
		  spanned by $S$. The problem of automatically generating
		  {\em optimal triangulations} for a point set $S$ has been a
		  subject of research since decades. As the number of
		  different triangulations of $S$ is an exponential function
		  of $n$, enumerating all possible triangulations and
		  selecting an optimal one (exhaustive search) is too
		  time-consuming even for small $n$. In fact, constructing
		  optimal triangulations in polynomial time is a challenging
		  task. Results on optimizing {\em combinatorial} properties
		  of triangulations, such as their degree or connectivity,
		  are rare. Most optimization criteria for which efficient
		  algorithms are known concern {\em geometric} properties of
		  the edges and triangles. The present survey article is
		  devoted to this topic.}
}

@InCollection{ax-ot-99,
  author	= {F. Aurenhammer and Y.-F.Xu},
  title		= {Optimal triangulations},
  booktitle	= {Encyclopedia of Optimization},
  publisher	= {Kluwer Academic Publishing},
  editor	= {C.A.Floudas, P.M.Pardalos},
  year		= 2000,
  pages		= {160--166},
  volume	= 4,
  note		= {[SFB Report F003-099, Tu Graz, Austria, 1998]},
  abstract	= {A {\em triangulation} of a given set $S$ of $n$ points in
		  the Euclidean plane is a maximal set of non-crossing line
		  segments spanned by $S$. The problem of automatically
		  generating {\em optimal triangulations} for a point set $S$
		  has been a subject of research since decades. As the number
		  of different triangulations of $S$ is an exponential
		  function of $n$, enumerating all possible triangulations
		  and selecting an optimal one (exhaustive search) is too
		  time-consuming even for small $n$. In fact, constructing
		  optimal triangulations in polynomial time is a challenging
		  task. Results on optimizing {\em combinatorial} properties
		  of triangulations, such as their degree or connectivity,
		  are rare. Most optimization criteria for which efficient
		  algorithms are known concern {\em geometric} properties of
		  the edges and triangles. The present survey article is
		  devoted to this topic.}
}

@InProceedings{dap-ssbi-10,
  author	= {M. Demuth and F. Aurenhammer and A. Pinz},
  title		= {Straight skeletons for binary shapes},
  booktitle	= {$3^{rd}$ Workshop on non-rigid shape analysis and
		  deformable image alignment (NORDIA'10)},
  year		= 2010,
  address	= {San Francisco, USA},
  abstract	= {This paper reviews the concept of straight skeletons,
		  which is well known in computational geometry, and applies
		  it to binary shapes that are used in vision-based shape and
		  object recognition. We devise a novel algorithm for
		  computing discrete straight skeletons from binary input
		  images, which is based on a polygonal approximation of the
		  input shape and a hybrid method that combines continuous
		  and discrete geometry. In our experiments, we analyze the
		  potential of straight skeletons in shape recognition, by
		  comparing their performance with medial-axis based shock
		  graphs on the Kimia shape databases. Our discrete straight
		  skeleton algorithm is not only outperforming typical
		  skeleton algorithms in terms of computational complexity,
		  it also delivers surprisingly good results in its
		  straightforward application to shape recognition.}
}

@InProceedings{haa-nrmwt-97,
  author	= {R. Hainz and O. Aichholzer and F. Aurenhammer},
  title		= {New results on minimum-weight triangulations and the {LMT}
		  skeleton},
  booktitle	= {Proc. $13^{th}$ European Workshop on Computational
		  Geometry CG '97},
  pages		= {4--6},
  year		= 1997,
  address	= {Wuerzburg, Germany},
  abstract	= {Let $P$ be a simple polygon in the plane and let $MWT(P)$
		  be a minimum-weight triangulation of $P$. We prove that the
		  $\beta$-skeleton of $P$ is a subset of $MWT(P)$ for all
		  values $\beta$ > $\sqrt{\frac{4}{3}}$ provided $P$ is
		  convex or near-convex. This settles the question of
		  tightness of this bound for a special case and gives
		  evidence for its validity in the general point set case.\\
		  We further disprove the conjecture that the so-called
		  $LMT$-skeleton coincides with the intersection of all
		  locally minimal triangulations, $LMT(P)$, even for convex
		  polygons $P$. We introduce an improved $LMT$-skeleton
		  algorithm which, for simple polygons $P$, exactly computes
		  $LMT(P)$, and thus a larger subgraph of $MWT(P)$. The
		  algorithm achieves the same in the general point set case
		  provided the connectedness of the improved $LMT$-skeleton,
		  which is given in allmost all practical instances.}
}