Zobrazeno 1 - 10
of 48
pro vyhledávání: '"Perkovic, Ljubomir"'
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bou
Externí odkaz:
http://arxiv.org/abs/1711.00068
Let ${\cal P}$ be a set of $n$ points embedded in the plane, and let ${\cal C}$ be the complete Euclidean graph whose point-set is ${\cal P}$. Each edge in ${\cal C}$ between two points $p, q$ is realized as the line segment $[pq]$, and is assigned a
Externí odkaz:
http://arxiv.org/abs/1603.03818
Autor:
Bonichon, Nicolas, Bose, Prosenjit, De Carufel, Jean-Lou, Perković, Ljubomir, Van Renssen, André
Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a competitive ratio of c if the length of the pa
Externí odkaz:
http://arxiv.org/abs/1501.01783
Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner, if for any pair of vertices u,v in E the distance between u and v in G
Externí odkaz:
http://arxiv.org/abs/1403.5350
In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs $G$ and $H$, each with a linear order defined on its vertices, a function $L$ that associates with every vertex in $G$ a list of vertices in $H$, and a pa
Externí odkaz:
http://arxiv.org/abs/1403.2009
In this paper we determine the stretch factor of the $L_1$-Delaunay and $L_\infty$-Delaunay triangulations, and we show that this stretch is $\sqrt{4+2\sqrt{2}} \approx 2.61$. Between any two points $x,y$ of such triangulations, we construct a path w
Externí odkaz:
http://arxiv.org/abs/1202.5127
Autor:
Kanj, Iyad A., Perkovic, Ljubomir
Publikováno v:
Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{del\approx 2.42$; however, its degre
Externí odkaz:
http://arxiv.org/abs/0802.2864
Autor:
Dennis, Michael1 michael_dennis@cs.berkeley.edu, Perkovic, Ljubomir2 lperkovic@cs.depaul.edu, Türkoglu, Duru2 duru@cs.uchicago.edu
Publikováno v:
Journal of Computational Geometry. 2021, Vol. 12 Issue 2, p86-125. 40p.
Publikováno v:
In Computational Geometry: Theory and Applications March 2015 48(3):237-250
Publikováno v:
In Journal of Computer and System Sciences 2007 73(6):892-907