Title: LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS
Abstract: Given a set P of n points in the plane such that each point has a positive weight, we study the problem of finding an obnoxious line that intersects the convex hull of P and maximizes the minimum weighted Euclidean distance to all points of P. We present an O(n 2 log n) time algorithm for the problem, improving the previously best-known O(n 2 log 3 n) time solution. We also consider a variant of this problem whose input is a set of m polygons with a total of n vertices in the plane such that each polygon has a positive weight and whose goal is to locate an obnoxious line with respect to the weighted polygons. An O(mn + n log 2 n log m + m 2 log n log 2 m) time algorithm for this variant was known previously. We give an improved algorithm of O(mn + n log 2 n + m 2 log n) time. Further, we reduce the time bound of a previous algorithm for the case of the problem with unweighted polygons from O((m 2 + n log m) log n) to O(m 2 + n log m).
Publication Year: 2012
Publication Date: 2012-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot