Finding a guard that sees most and a shop that sells most

We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set in the plane. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time, and the rigid motion doing so in near-cubic time.
Publisher
SPRINGER
Issue Date
2007-05
Language
ENG
Keywords

COMPUTATIONAL GEOMETRY; VORONOI GAME; OVERLAP; AREA; GALLERIES; POLYGONS

Citation

DISCRETE & COMPUTATIONAL GEOMETRY, v.37, no.4, pp.545 - 563

ISSN
0179-5376
URI
http://hdl.handle.net/10203/316
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
ceh-fgsmssm.pdf(291.72 kB)Download
  • Hit : 488
  • Download : 1818
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 20 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0