Matemáticas

URI permanente para esta comunidadhttps://hdl.handle.net/11441/33995

Examinar

Mostrando 1 - 5 de 5

A quadratic distance bound on sliding between crossing-free spanning trees
(2004) Aichholzer, Oswin; Reinhardt, Klaus
Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide operations. No polynomial upper bound for this task has been known, but in O.Aichholzer, F.Aurenhammer, F.Hurtado Sequences of spanning trees and a fixed tree theorem. Computational Geometry: Theory and Applications, 21(1-2):3-20, 2002. a bound of O(n2 log n) operations was conjectured.
Flips in combinatorial pointed pseudo-triangulations with face degree at most four
(2013) Aichholzer, Oswin; Hackl, Thomas; Orden Martín, David; Pilz, Alexander; Saumell Mendiola, María; Vogtenhuber, Birgit; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the flip graph of combinatorial 4-PPTs with triangular outer face is connected and has diameter O(n2).
On the number of pseudo-triangulations of certain point sets
(2004) Aichholzer, Oswin; Orden Martín, David; Santos Leal, Francisco; Speckmann, Bettina
We compute the exact number of pseudo-triangulations for two prominent point sets, namely the so-called double circle and the double chain. We also derive a new asymptotic lower bound for the maximal number of pseudotriangulations which lies significantly above the related bound for triangulations.
Simulating distributed algorithms for lattice agents
(2013) Aichholzer, Oswin; Hackl, Thomas; Sacristán Adinolfi, Vera; Vogtenhuber, Birgit; Wallner, Reinhardt; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
We present a practical Java tool for simulating synchronized distributed algorithms on sets of 2-and 3-dimensional square/cubic lattice-based agents. This AgentSystem assumes that each agent is capable to change position in the lattice and that neighboring agents can attach and detach from each other. In addition, it assumes that each module has some constant size memory and computation capability, and can send/receive constant size messages to/from its neighbors. The system allows the user to dene sets of agents and sets of rules and apply one to the other. The AgentSystem simulates the synchronized execution of the set of rules by all the modules, and can keep track of all actions made by the modules at each step, supporting consistency warnings and error checking. Our intention is to provide a useful tool for the researchers from geometric distributed algorithms.
Triangulations without pointed spanning trees
(2004) Aichholzer, Oswin; Huemer, Clemens; Krasser, Hannes
Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.

Examinar

Examinando Matemáticas por Autor "Aichholzer, Oswin"