On Finding a Guard that Sees Most and a Shop that Sells Most

Otfried Cheong; Alon Efrat; Sariel Har-Peled

On Finding a Guard that Sees Most and a Shop that Sells Most

Otfried Cheong, Alon Efrat, Sariel Har-Peled

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.

Original language	English (US)
Pages	1091-1100
Number of pages	10
State	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004

Other

Other	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	1/11/04 → 1/13/04

ASJC Scopus subject areas

Software
Mathematics(all)

Library availability

Discover UIUC Full Text

Cite this

@conference{a2b9ad8e02ff4085ad775aa378cfd232,

title = "On Finding a Guard that Sees Most and a Shop that Sells Most",

abstract = "We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.",

author = "Otfried Cheong and Alon Efrat and Sariel Har-Peled",

year = "2004",

language = "English (US)",

pages = "1091--1100",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - On Finding a Guard that Sees Most and a Shop that Sells Most

AU - Cheong, Otfried

AU - Efrat, Alon

AU - Har-Peled, Sariel

PY - 2004

Y1 - 2004

N2 - We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.

AB - We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.

UR - http://www.scopus.com/inward/record.url?scp=1842538784&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1842538784&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:1842538784

SP - 1091

EP - 1100

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

On Finding a Guard that Sees Most and a Shop that Sells Most

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this