Computing a planar widest empty α-siphon in o(n3) time

Boaz Ben-Moshe; Binay K. Bhattacharya; Sandip Das; Daya R. Gaur; Qiaosheng Shi

Computing a planar widest empty α-siphon in o(n³) time

Boaz Ben-Moshe
, Binay K. Bhattacharya
, Sandip Das
, Daya R. Gaur
, Qiaosheng Shi

Department of Computer Science

نتاج البحث: نتاج بحثي من مؤتمر › محاضرة › مراجعة النظراء

1 اقتباس (Scopus)

ملخص

Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that min_p∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n³) time and space. The previous best running time for this problem was O(n³ log² n) time [2].

اللغة الأصلية	الإنجليزيّة
الصفحات	33-36
عدد الصفحات	4
حالة النشر	نُشِر - 2007
الحدث	19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, كندا المدة: 20 أغسطس 2007 → 22 أغسطس 2007

!!Conference

!!Conference	19th Annual Canadian Conference on Computational Geometry, CCCG 2007
الدولة/الإقليم	كندا
المدينة	Ottawa, ON
المدة	20/08/07 → 22/08/07

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@conference{301ca3d9e36d4960a9b7327c6a1e4b0b,

title = "Computing a planar widest empty α-siphon in o(n3) time",

abstract = "Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].",

author = "Boaz Ben-Moshe and Bhattacharya, \{Binay K.\} and Sandip Das and Gaur, \{Daya R.\} and Qiaosheng Shi",

year = "2007",

language = "אנגלית",

pages = "33--36",

note = "19th Annual Canadian Conference on Computational Geometry, CCCG 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}

TY - CONF

T1 - Computing a planar widest empty α-siphon in o(n3) time

AU - Ben-Moshe, Boaz

AU - Bhattacharya, Binay K.

AU - Das, Sandip

AU - Gaur, Daya R.

AU - Shi, Qiaosheng

PY - 2007

Y1 - 2007

N2 - Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].

AB - Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].

UR - https://www.scopus.com/pages/publications/69049088913

M3 - ???researchoutput.researchoutputtypes.contributiontoconference.paper???

AN - SCOPUS:69049088913

SP - 33

EP - 36

T2 - 19th Annual Canadian Conference on Computational Geometry, CCCG 2007

Y2 - 20 August 2007 through 22 August 2007