Finding shadows among disks

N. Jovanovic; J.H.M. Korst; Z. Aleksovski; W.P.A.J. Michiels; J.J. Lukkien; E.H.L. Aarts

Finding shadows among disks

N. Jovanovic, J.H.M. Korst, Z. Aleksovski, W.P.A.J. Michiels, J.J. Lukkien, E.H.L. Aarts

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.

Originele taal-2	Engels
Titel	Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012
Pagina's	89-94
Status	Gepubliceerd - 2012
Evenement	24th Canadian Conference on Computational Geometry (CCCG 2012) - Charlottentown, Canada Duur: 8 aug. 2012 → 10 aug. 2012 Congresnummer: 24 http://2012.cccg.ca/

Congres

Congres	24th Canadian Conference on Computational Geometry (CCCG 2012)
Verkorte titel	CCCG
Land/Regio	Canada
Stad	Charlottentown
Periode	8/08/12 → 10/08/12
Ander	24th Canadian Conference on Computational Geometry
Internet adres	http://2012.cccg.ca/

Citeer dit

@inproceedings{ee977ab300d046daaf11de7347ba8657,

title = "Finding shadows among disks",

abstract = "Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.",

author = "N. Jovanovic and J.H.M. Korst and Z. Aleksovski and W.P.A.J. Michiels and J.J. Lukkien and E.H.L. Aarts",

year = "2012",

language = "English",

pages = "89--94",

booktitle = "Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012",

note = "24th Canadian Conference on Computational Geometry (CCCG 2012), CCCG ; Conference date: 08-08-2012 Through 10-08-2012",

url = "http://2012.cccg.ca/",

}

Jovanovic, N, Korst, JHM, Aleksovski, Z, Michiels, WPAJ , Lukkien, JJ & Aarts, EHL 2012, Finding shadows among disks. in Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012. blz. 89-94, 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottentown, Canada, 8/08/12.

TY - GEN

T1 - Finding shadows among disks

AU - Jovanovic, N.

AU - Korst, J.H.M.

AU - Aleksovski, Z.

AU - Michiels, W.P.A.J.

AU - Lukkien, J.J.

AU - Aarts, E.H.L.

N1 - Conference code: 24

PY - 2012

Y1 - 2012

N2 - Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.

AB - Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.

M3 - Conference contribution

SP - 89

EP - 94

BT - Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012

T2 - 24th Canadian Conference on Computational Geometry (CCCG 2012)

Y2 - 8 August 2012 through 10 August 2012

ER -

Finding shadows among disks

Samenvatting

Congres

Vingerafdruk

Citeer dit