New and improved spanning ratios for Yao graphs

Autor: Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, Ge Xia

Publikováno v: Journal of Computational Geometry, Vol 6, Iss 2 (2015)

For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for

Externí odkaz: https://doaj.org/article/5a1e46b0dea642a4bcd40d008b76bf3a

Flipping edge-labelled triangulations

Autor: Vinayak Pathak, Prosenjit Bose, Anna Lubiw, Sander Verdonschot

Publikováno v: Computational Geometry. 68:309-326

Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b8f91a3ab693eb715f839116fd61bf8a
https://doi.org/10.1016/j.comgeo.2017.06.005

Reconstructing a Convex Polygon from Its $$\omega $$ ω -cloud

Autor: Sander Verdonschot, Jean-Lou De Carufel, Prosenjit Bose, Elena Arseneva

Publikováno v: Computer Science – Theory and Applications ISBN: 9783030199548
CSR

An \(\omega \)-wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle \(\omega < \pi \). Given a convex polygon P, we place the \(\omega \)-wedge such that P is in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ab467cd49cc735111024f21f1e373838
https://doi.org/10.1007/978-3-030-19955-5_3

Towards tight bounds on theta-graphs: More is not always better

Autor: Jean-Lou De Carufel, Pat Morin, Sander Verdonschot, Prosenjit Bose, André van Renssen

Publikováno v: Theoretical Computer Science. 616:70-93

We present improved upper and lower bounds on the spanning ratio of ?-graphs with at least six cones. Given a set of points in the plane, a ?-graph partitions the plane around each vertex u into m disjoint cones, each having aperture ? = 2 π / m , a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::bb341549dc93c2500cc68d7c5e6e3458
https://doi.org/10.1016/j.tcs.2015.12.017

Continuous Yao graphs

Autor: Jean-Lou De Carufel, Perouz Taslakian, Sander Verdonschot, Davood Bakhshesh, Luis Barba, Mirela Damian, Mohammad Farshi, André van Renssen, Rolf Fagerberg, Prosenjit Bose

Publikováno v: Bakhshesh, D, Barba, L, Bose, P, De Carufel, J L, Damian, M, Fagerberg, R, Farshi, M, van Renssen, A, Taslakian, P & Verdonschot, S 2018, ' Continuous Yao graphs ', Computational Geometry: Theory and Applications, vol. 67, pp. 42-52 . https://doi.org/10.1016/j.comgeo.2017.10.002

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points S ⊂ R 2 and an angle 0 θ ⩽ 2 π , we define the continuous Yao graph c Y ( θ ) with vertex set S and angle θ as follows. For each p , q ∈ S , we ad

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bb26dd8d2c2234bcd02db8f5c680b044
https://findresearcher.sdu.dk:8443/ws/files/137375829/Continuous_Yao_graphs.pdf