یک ساختار داده پویا برای یافتن موثر نقاط زیر یک خط و تخمین تعداد آنها

خلاصه

یک سوال اساسی در هندسه محاسباتی این است که چگونه می توان رابطه بین مجموعه ای از نقاط و یک خط را در یک صفحه واقعی پیدا کرد. در این مقاله، ساختارهای داده چند بعدی را برای N نقطه ارائه می‌کنیم که امکان پاسخگویی به پرسش‌های زیر را برای هر خط ورودی داده شده فراهم می‌کند: (1) تخمین در

O (\log N)

زمان تعداد نقاط زیر خط. (2) بازگشت به داخل

O (\log N + k)

زمان

k \leq N

نقاطی که زیر خط هستند؛ و (3) بازگشت به داخل

O (\log N)

زمان نزدیکترین نقطه به خط. ما کاربرد این سوال محاسباتی را با کاربردهای GIS در دفاع هوایی و کنترل ترافیک نشان می دهیم.

کلید واژه ها:

ساختار داده های مکانی ; پرس و جوهای مکان نقطه ; پرس و جوهای نزدیکترین نقطه تخمین گزینش پذیری

1. معرفی

1.1. بیان مشکل و بررسی اجمالی نتایج

در حوزه‌های هندسه محاسباتی و پایگاه‌های داده فضایی [ 1 ، 2 ، 3 ، 4 ، 5 ]، یک سوال اساسی این است که چگونه می‌توان برای یک مجموعه معین از N نقطه در یک صفحه، تعداد نقاطی را که زیر یک خط دلخواه قرار دارند، پیدا کرد. . برای پاسخگویی موثر به دنباله ای از پرس و جوها از این نوع، هدف یافتن یک ساختار داده شاخص برای مجموعه ای از نقاط داده شده است به طوری که برای هر خط دلخواه پاسخ را بتوان در

O (\log N)

زمان.

تخمین انتخابی به معنای یافتن تعداد نقاط یا نقاط متحرکی است که تقریباً شرایط مختلف را برآورده می کنند. تخمین گزینش یک مشکل مهم در پرس و جو پایگاه داده مکانی و مکانی- زمانی است زیرا برآورد ارزیابی پرس و جو را هدایت می کند [ 4 ، 6 ، 7 ]. تخمین گزینش پذیری برای اجسام نقطه متحرک توسط اندرسون و ریوز [ 8 ]، چوی و چانگ [ 9 ] و سان و همکاران در نظر گرفته شد. [ 10 ]، که الگوریتم های مختلفی را برای تخمین تعداد نقاط متحرکی که در یک ناحیه جعبه یا ناحیه هایپرباکس خاص در زمان t آینده خواهند بود، توصیف کردند .

مشکل تخمین تعداد نقاط زیر یک خط برای موارد جدید تخمین گزینش پذیری در پرس و جوی پایگاه داده شی مکانی-زمانی یا متحرک قابل استفاده است. اگر تمام نقاط متحرک در امتداد محور x حرکت کنند ، مجموعه ای از نقاط متحرک خطی

P_{i} (t) = a_{i} t + b_{i}

را می توان به عنوان مجموعه S از نقاط استاتیک نشان داد

(a_{i}, b_{i})

در صفحه دوگانه استاتیک [ 1 ، 2 ، 3 ]. بنابراین، مشکل یافتن نقاط متحرکی که در سمت چپ یک نقطه پرس و جوی متحرک دلخواه فرم قرار دارند

Q (t) = a t + b

در زمان t معادل یافتن نقاطی در S است که زیر خط ℓ که از آن عبور می کند

(a, b)

با شیب

- t

در هواپیمای دوگانه

در برنامه های کاربردی دیگری که مجموعه نقاطی که در زیر یک خط قرار دارند باید برگردانده شوند، پاسخ دادن به پرس و جو می تواند بسیار کندتر باشد. بهترین چیزی که می توان برای آن هدف قرار داد یک ساختار داده بر روی N نقطه است به گونه ای که بتوانیم تمام نقاطی را که زیر یک خط هستند برگردانیم.

O (\log N + k)

زمان، که k تعداد نقاطی است که در زیر خط قرار دارند. اینجا، نماد

O (\log N + k)

نشان می دهد که تعداد مراحل محاسبات پایه مورد نیاز متناسب با لگاریتم N و متناسب با k است . بدیهی است که نوشتن k نقاط مربوط به خروجی را نمی توان انتظار داشت که سریعتر از زمان خطی (به k ) انجام شود. با این حال، نکته مهم در اینجا این است که، اگر نوشتن خروجی را نادیده بگیریم، بخش جستجوی این مشکل زمان لگاریتمی (به N ) می گیرد که بهترین پیچیدگی زمانی است که می توانیم برای جستجو انتظار داشته باشیم.

ما در این مقاله یک ساختار داده پویا، بر اساس درختان AVL برای ذخیره پیکربندی نقاط در صفحه پیشنهاد می‌کنیم. درختان AVL که به نام های Adelson-Velsky و Landis [ 11 ] نامگذاری شده اند، درختان جستجوی دودویی هستند. درخت‌های AVL «متعادل» باقی می‌مانند، به این معنا که برای هر گره، ارتفاع زیردرخت سمت چپ و زیردرخت سمت راست حداکثر یک تفاوت دارند. با استفاده از درختان AVL، رویکرد پیشنهادی ما پویا می شود به این معنا که افزودن یا حذف یک نقطه در مجموعه اصلی N نقطه، منجر به هزینه به روز رسانی می شود.

O (N^{2} \log N)

درخت AVL هزینه ساخت ساختار داده بر اساس درختان AVL می باشد

O (N^{3})

، هم در مکان و هم در زمان. یکی دیگر از مزایای رویکرد ما این است که می توان آن را برای پاسخ به مسئله (3) تطبیق داد: با توجه به یک خط ورودی، نقطه ای را که نزدیکترین خط به خط است برگردانید.

این به این معنی است که در هر یک از گره های آن، موارد با مقدار کلید کمتر از گره در زیردرخت فرزند سمت چپ و مقادیر بزرگتر از مقدار کلید از گره در زیردرخت فرزند سمت راست ذخیره می شوند. درخت‌های جستجوی دودویی که m کلید-مقدار را ذخیره می‌کنند، در حالت ایده‌آل، امکان جستجوی یک مقدار کلید معین را در زمان می‌دهند

O (\log m)

. این پیچیدگی زمانی زمانی رخ می‌دهد که درخت‌های باینری نسبتاً متعادل باشند. در حالی که بسیاری از روش‌های درج و حذف گره ممکن است منجر به درخت‌های جستجوی باینری نامتعادل شوند (با پیچیدگی جستجو که ممکن است تبدیل شود).

O (m)

، به جای

O (\log m)

روش درختی AVL به صورت پویا درخت AVL را پس از درج یا حذف گره ها با اعمال دنباله ای از چرخش ها یا چرخش های مضاعف متعادل می کند [ 11 ].

ما این مقدمه را با بحث در مورد برخی از سناریوهای کاربردی و کارهای مرتبط به پایان می بریم.

1.2. سناریوهای کاربردی

طیف وسیعی از کاربردهای ممکن برای الگوریتم های پیشنهادی ما وجود دارد. در زیر به طور خلاصه دو برنامه انتخاب شده را توضیح می دهیم. اولی مربوط به پدافند هوایی و دیگری مربوط به کنترل ترافیک است.

سناریوی کاربردی 1:

فرض کنید نقشه ای داریم که در آن خانه ها در یک منطقه کلانشهری قرار گرفته اند که باد از سمت شمال می وزد. همچنین فرض کنید که یک هواپیمای دشمن در یک خط از سراسر قلمرو عبور می کند و به طور مداوم تعدادی سلاح زیستی را پرتاب می کند. سپس، برای تخمین تعداد افرادی که ممکن است در معرض خطر فوری باشند، باید تعداد خانه‌های زیر خطی که مسیر هواپیما است را پیدا کنیم و سپس تعداد خانه‌ها را با میانگین تراکم افراد در هر خانه ضرب کنیم. آن منطقه شهری

سناریوی کاربردی 2:

فرض کنید که یک ایستگاه پلیس در حال نظارت بر بخشی از بزرگراهی است که در جهت شرق-غرب حرکت می کند. فرض کنید خودروهایی که به سمت شرق حرکت می کنند (موازی با محور x ) هستند

C_{1}, \dots, C_{n}

. موقعیت مکانی هر ماشین

C_{i}

را می توان به عنوان یک تابع تخمین زد

a_{i} t + b_{i}

، جایی که

b_{i}

محل اولیه ماشین است و

a_{i}

سرعت آن است. n ماشین را می توان در یک صفحه دوتایی استاتیک، جایی که هر کدام نشان داد

C_{i}

با نقطه نشان داده می شود

(a_{i}, b_{i})

[ 4 ]. فرض کنید، در زمان t ، یک خودروی دلخواه، به عنوان مثال، خودرو

C_{5}

، به دلیل پنچری لاستیک یا عیب دیگری ناگهان متوقف می شود. برای پیدا کردن تعداد ماشین هایی که پشت سر هستند

C_{5}

و احتمالاً تحت تأثیر تصادف قرار می گیرند، باید در صفحه دوگانه تعداد نقاط زیر خطی را که از نقطه عبور می کند پیدا کنیم.

(a_{5}, b_{5})

و دارای شیب است

- t

(به قضیه 20.4.3 در [ 4 ] مراجعه کنید). تخمین سریع تعداد خودروهایی که ممکن است تحت تأثیر تصادف قرار گیرند، برای محاسبه تعداد افسران پلیسی که ممکن است به محل حادثه اعزام شوند و برای سایر مسافرانی که قصد ورود به بزرگراه را دارند، توصیه ای برای انحراف صادر می کند. تعداد خودروهای آسیب دیده بالاتر از یک آستانه مشخص است.

پیاده سازی نرم افزار بالقوه :

اگرچه، طبق دانش ما، نرم افزار GIS کنونی شامل عملگرهای داخلی نقاط خطی نمی شود، آنها اغلب شامل برخی از عملگرهای فضایی مرتبط هستند. به عنوان مثال، ST_Distance در PostGIS به عنوان یک عملگر نزدیکترین نقطه در دسترس است، یعنی از مجموعه ای از نقاط، نقطه(هایی) را می یابد که نزدیکترین نقطه به نقطه معین هستند [12 ] . سایر اپراتورهای مجاورت فضایی نیز در ArcGIS برای توسعه دهندگان و گزینه فضایی و نمودار اوراکل برای پایگاه داده اوراکل (نسخه) موجود هستند

12^{c}

) [ 13 ]، اما آنها با عملگر نقاط خط پیشنهادی ما [ 12 ] متفاوت هستند. از این رو، می‌تواند فرصتی برای استفاده از اپراتور نقاط خط جدید ما در چندین سیستم GIS وجود داشته باشد. به عنوان مثال، سیستم MLPQ خود ما [ 14 ]، که برای برنامه های GIS طراحی شده است و از پسوند SQL به عنوان یک زبان پرس و جو استفاده می کند، می تواند به راحتی یک عملگر نقاط خط را اتخاذ کند.

L i n e P o i n t s (x, y, x 1, y 1, x 2, y 2, k)

به عنوان یک اپراتور داخلی را

L i n e P o i n t s

اپراتور تعداد نقاط k را در یک رابطه فضایی پیدا می کند

R (x, y)

که زیر خطی هستند که از نقاط عبور می کند

(x 1, y 1)

(x 2, y 2)

به عنوان مثال، فرض کنید که $(x 1, y 1)$ و $(x 2, y 2)$ دو نقطه در مسیر خطی هواپیما در سناریوی کاربردی 1 هستند. مسیر را می توان با رابطه نشان داد $T r a j e c t o r y (x 1, y 1, x 2, y 2)$ . آن رابطه را نیز فرض کنید $H o u s e s (x, y)$ مکان خانه ها در منطقه کلان شهر هستند. سپس، تعداد خانه هایی که ممکن است تحت تأثیر حمله سلاح های زیستی قرار گیرند را می توان با پرس و جوی SQL زیر پیدا کرد:

انتخاب کنید	LinePoints.k
از جانب	خانه ها، نقاط خط، مسیر
جایی که	LinePoints.x = Houses.x و LinePoints.y = Houses.y و
	LinePoints.x1 = Trajectory.x1 AND LinePoints.y1 = Trajectory.y1 و
	LinePoints.x2 = Trajectory.x2 و LinePoints.y2 = Trajectory.y2.

1.3. کار مرتبط

یکی از مسائلی که در این مقاله به آن پرداخته می شود، به عنوان مسئله پرس و جو دامنه نیمه صفحه نیز شناخته می شود و یک راه حل کارآمد توسط Chazelle، Guibas و Lee در سال 1983 [ 15 ] ارائه شد . روش این نویسندگان امکان پاسخگویی به پرس و جو محدوده نیم صفحه را در داخل فراهم می کند

O (\log N + k)

زمان، با استفاده از

O (N)

فضا و

O (N \log N)

زمان پیش پردازش روش آنها بر اساس اصول دوگانگی هندسی است و بر روش هایی مانند الگوریتم مکان نقطه مسطح بهینه کرک پاتریک تکیه دارد. اگرچه، در تئوری، الگوریتم کرک پاتریک به یک بهینه دست می یابد

O (\log N)

زمان پرس و جو به دلیل ساخت بسیار هوشمندانه آن، به نظر می رسد که در عمل، وجود برخی عوامل ثابت جاسازی شده بزرگ در پیچیدگی زمانی آن، آن را کمتر امکان پذیر می کند. در نتیجه، در عمل به ندرت از آن استفاده می شود. به دلیل این اتکا، عملی بودن روش پیشنهادی توسط این نویسندگان مورد تردید قرار گرفته است. در واقع، با گذشت بیش از سی سال از انتشار آن، می بینیم که روش Chazelle، Guibas و Lee به سختی در عمل استفاده می شود (مثلاً در سیستم های پایگاه داده) و هیچ نرم افزاری در متون علمی یا کتاب های درسی در این زمینه ذکر نشده است. الگوریتم های GIS [ 16]. روش پیشنهادی در این مقاله نه تنها بر روی ساختارهای داده پرکاربرد (مانند درختان AVL) تکیه می‌کند و پیاده‌سازی آن آسان‌تر است، بلکه اطلاعات مرتب‌سازی نقاط را نسبت به یک خط نیز ضبط می‌کند. تفاوت دیگر این است که ما نزدیکترین نقطه را نیز به یک پرس و جو خط می کنیم.

این مقاله به شرح زیر سازماندهی شده است. بخش 2 راه حلی را توضیح می دهد که تعداد نقاط زیر یک خط را تقریبی می کند. بخش 3 راه حلی را ارائه می دهد که تعداد دقیق نقاط زیر خط را نشان می دهد. بخش 4 راه حلی برای مشکل یافتن نزدیکترین نقطه به یک خط ارائه می کند. در نهایت، بخش 5 برخی از نتیجه گیری ها و مشکلات باز را ارائه می دهد.

2. تقریب تعداد نقاط زیر یک خط

اجازه دهید

R

مجموعه اعداد واقعی را نشان دهید و اجازه دهید

R^{2}

هواپیمای واقعی باشد در این بخش، ساختار داده‌های شاخص را برای مجموعه‌ای P از N نقطه در نظر می‌گیریم

R^{2}

که به شما امکان می دهد تقریبی از تعداد نقاط زیر یک خط را به طور موثر پیدا کنید. با چند تعریف شروع می کنیم. یک نقطه

(a_{1}, b_{1})

بر نقطه دیگری تسلط دارد

(a_{2}, b_{2})

که در

R^{2}

اگر و تنها اگر

a_{2} \leq a_{1}

b_{2} \leq b_{1}

تعریف 1.

در زیر از سه علامت اختصاری زیر استفاده می کنیم:

(1): $# A p p r o x (ℓ, P)$ تعداد تخمینی نقاط در P زیر یک خط ℓ است.
(2): $# B e l o w (ℓ, P)$ تعداد دقیق نقاط P در زیر یک خط ℓ است.
(3): $# D o m (p, P)$ تعداد نقاطی در S است که نقطه p بر آنها غالب است.

قضیه بعدی بهبود نتیجه پیچیدگی در مورد همان مسئله در [ 17 ] است.

قضیه 1.

# A p p r o x (ℓ, P)

را می توان در یافت

O (\log N)

زمان و

O (N \log N)

فضا، که در آن N تعداد نقاط P است.

اثبات

ما می توانیم یک ساختار داده ای داشته باشیم که مختصات x را مرتب می کند و یک ساختار داده جداگانه که مختصات y نقاط N را مرتب می کند . سپس، حداقل و حداکثر مختصات x ،

x_{\min}

x_{\max}

و حداقل و حداکثر مختصات y ،

y_{\min}

y_{\max}

، همیشه می توان در پیدا کرد

O (\log N)

زمان و

O (N)

فضا.

وقتی ℓ یک خط افقی باشد

y = a

یا یک خط عمودی

x = b

، سپس مشکل به یافتن کاهش می یابد

# D o m (p, P)

، جایی که

p = (x_{\max}, a)

یا

p = (b, y_{\max})

، به ترتیب. شماره

# D o m (p, P)

را می توان در یافت

O (\log N)

زمان و

O (N \log N)

فضا با استفاده از ساختار داده ECDF-tree شناخته شده [ 18 ]. در اینجا، ECDF به اختصار “تابع توزیع تجمعی تجربی” را بیان می کند.

اگر ℓ نه افقی و نه عمودی است، ℓ را بر تقسیم کنید $m - 1$ افقی و $m - 1$ خطوط عمودی، جایی که $m \geq 2$ هر ثابت است از آنجایی که نقاط N همه در یک کادر با گوشه سمت چپ پایین قرار دارند $(x_{\min}, y_{\min})$ و یک گوشه سمت راست بالا $(x_{\max}, y_{\max})$ ، خطوط عمودی و افقی می توانند آن کادر را به دو قسمت تقسیم کنند $m^{2}$ جعبه های کوچکتر با اندازه مساوی شکل 1 چنین تقسیمی از ℓ را نشان می دهد $m = 4$ . این تقسیم بندی امکان کاهش مشکل یافتن را فراهم می کند $# B e l o w (ℓ, P)$ برای یافتن دنباله ای از $# D o m (p, P)$ مقادیر به شرح زیر است:

(1): مستطیلی را بیابید که شامل تمام نقاط P باشد .
(2): قسمت ℓ داخل مستطیل را با قطعات خط افقی و عمودی به m تعداد قطعات مساوی ببرید. نقاط جدید ایجاد شده توسط برش ها را به عنوان شماره گذاری کنید $A_{1}, \dots, A_{m + 1}$ ، $B_{1}, \dots, B_{m}$ ، و $C_{1}, \dots, C_{m}$ همانطور که در شکل 1 نشان داده شده است .
(3): تعداد نقاطی که احتمالاً کمتر از ℓ هستند ، بر اساس نقاط B ، یک کران بالایی برای $# B e l o w (ℓ, P)$ :

$# B e l o w (ℓ, P) \leq # D o m (آ m + 1 ، پ) + \sum i = 1 متر # D o m (ب من ، پ) - # D o m (آ من + 1 ، پ) .$
(4): تعداد نقاطی که مطمئناً زیر ℓ هستند ، بر اساس نقاط C ، یک کران پایین برای $# B e l o w (ℓ, P)$ :

$# B e l o w (ℓ, P) \geq # D o m (آ m + 1 ، پ) + \sum i = 1 متر # دی o m (آ من ، پ) - # D o m (سی من ، پ) .$
(5): $# B e l o w (ℓ, P)$ می توان به عنوان میانگین کران بالا و پایین بالا تقریب زد:

$# D o m ( آ 1 ، پ ) + # D o m ( آ m + 1 ، پ ) + \sum متر i = 1 # D o m ( ب من ، پ ) - # D o m ( سی من ، پ ) 2 .$

قضیه از $O (N \log N)$ فضا و $O (\log N)$ زمان مورد نیاز الگوریتم ECDF و این واقعیت که تقریب در (5) فقط نیاز دارد $2 (m + 1)$ فراخوانی به الگوریتم ECDF ☐

مثال 1.

شکل 1 مجموعه ای از نقاط درون یک مستطیل و خطی را نشان می دهد که از مستطیل عبور می کند. خط عبور به داخل قطع می شود

m = 4

قطعات به صورت افقی توسط بخش های خط اتصال

C_{i}

B_{i + 1}

برای

1 \leq i \leq 3

و به صورت عمودی توسط بخش های خط متصل می شود

B_{j}

C_{j + 1}

برای

1 \leq j \leq 3

. در شکل 1 کران پایین 5 و کران بالایی 9 است و میانگین اینها 7 است که دقیقاً تعداد نقاط زیر خط است.

در الگوریتم تقریب قضیه 1 از ثابت m استفاده کردیم . می توان ثابت m را که در الگوریتم تقریب استفاده می شود تغییر داد. ما می توانیم به واقعیت زیر توجه کنیم.

نتیجه 1.

مانند

m \to + \infty

# A p p r o x (ℓ, P) = # B e l o w (ℓ, P)

اثبات

با افزایش m ، نواحی مثلثی که مرزهای پایینی و بالایی آن با ناحیه واقعی زیر خط تفاوت دارند، به طور فزاینده ای کوچکتر می شوند. از این رو، دقت تقریب تمایل به افزایش دارد. در حد، مناطق مثلثی ناپدید می شوند و تقریب دقیقاً مقدار را نشان می دهد

# B e l o w (ℓ, P)

. ☐

گاهی اوقات می توان یک شمارش دقیق را برای مقادیر نسبتاً کوچک m تضمین کرد . نمونه ای از چنین تضمینی بر اساس کوتاه ترین فاصله هر نقطه تا خط بعداً در نتیجه 2 مورد بحث قرار می گیرد.

از آنجایی که درختان ECDF در ابعاد بالاتر قابل اجرا هستند، الگوریتم تقریب فوق را می توان به ابعاد بالاتر نیز گسترش داد. به عنوان مثال، در سه بعد، تقریب با استفاده از پرس و جوهای تسلط نقطه تنظیم با استفاده از درختان ECDF، تعداد نقاط زیر یک صفحه را پیدا می کند. در این مورد، هواپیما با استفاده از یک شبکه موازی با محورها بریده می شود.

3. یک جستجوی موقعیت مکانی با توجه به یک خط

در این بخش الگوریتمی را ارائه می کنیم که با توجه به مجموعه ای محدود

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

از N نقطه در

R^{2}

، یک ساختار داده می سازد

L (P)

از اندازه

O (N^{2})

. ساختار داده

L (P)

می توان برای پاسخ به پرسش زیر استفاده کرد

O (\log N)

زمان: به عنوان ورودی یک خط ℓ در داده می شود

R^{2}

نقاط P که زیر ℓ هستند ، نقاط P که روی ℓ هستند و نقاط P که بالای ℓ هستند را برگردانید .

الگوریتم دوم یک خط ℓ را به عنوان ورودی به شکل سه گانه دریافت می کند

(a, b, c)

از اعداد حقیقی که ℓ را با معادله تعیین می کنند

a x + b y + c = 0

. در عمل، این اعداد حقیقی a ، b و c باید به طور محدود قابل نمایش باشند. مثلاً می‌توانیم آنها را به‌عنوان اعداد واقعی یا گویا قابل محاسبه در نظر بگیریم.

ما دوست داریم بتوانیم مقادیر را سفارش دهیم

a x_{i} + b y_{i} + c

، برای

i = 1, \dots, N

، به طوری که به راحتی می توان دید که کدامیک از آنها کوچکتر، مساوی یا بزرگتر از 0 هستند. در واقع، آن نقاط

(x_{i}, y_{i})

از P که برای آن

a x_{i} + b y_{i} + c > 0

بالای خط ℓ هستند ، آن نقاطی از P که برای آنها

a x_{i} + b y_{i} + c = 0

روی خط ℓ و آن نقاط P هستند که برای آنها

a x_{i} + b y_{i} + c < 0

زیر خط ℓ هستند . بنابراین، سفارش مقادیر

a x_{i} + b y_{i} + c

و تعیین شاخص هایی که علامت از − به 0 و سپس به + تغییر می کند، امکان پاسخ دادن به پرسش فوق را در زمان ثابت می دهد (به غیر از نوشتن پاسخ، که لزوماً زمان خطی می برد). به راحتی می توان متوجه شد که ترتیب مقادیر

a x_{i} + b y_{i} + c

مستقل از c است .

بدیهی است که وجود دارد $N!$ ترتیب احتمالی عناصر P ، یا به طور معادل، شاخص های آنها. در واقع، هر سفارش $i_{1} < i_{2} < \dots < i_{N}$ از عناصر مجموعه ${1, 2, . . ., N}$ را می توان به عنوان جایگشت این مجموعه در نظر گرفت. جایگشت را می نویسیم که 1 به آن نگاشت شده است $i_{1}$ ; 2 به نقشه برداری شده است $i_{2}$ ، ….، و N به نگاشت می شود $i_{N}$ مانند $(i_{1}, \dots, i_{N}) .$ گروه همه جایگشت های مجموعه را نشان می دهیم ${1, 2, . . ., N}$ توسط $S_{N}$ . برای $(i_{1}, \dots, i_{N}) \in S_{N}$ ، می توانیم زیر مجموعه را در نظر بگیریم $A (i_{1}, \dots, i_{N})$ از تاپل ها $(a, b) \in R^{2}$ برای کدام

آ ایکس من 1 + ب y من 1 + c \leq a ایکس من 2 + ب y من 2 + c \leq \dots \leq a ایکس من ن - 1 + ب y من ن - 1 + c \leq a ایکس من ن + ب y من ن + ج .

نابرابری های فوق را می توان به طور معادل، مستقل از c ، as نوشت

آ ایکس من 1 + ب y من 1 \leq الف ایکس من 2 + ب y من 2 \leq \dots \leq الف ایکس من ن - 1 + ب y من ن - 1 \leq الف ایکس من ن + ب y من ن .

(†)

مجموعه ها

A (i_{1}, \dots, i_{N})

که از این طریق تعیین می شود، زیرمجموعه های خطی و نیمه جبری دو بعدی هستند.

(a, b)

-سطح. قبلاً اشاره کردیم که حداکثر وجود دارد

N!

چنین مجموعه های ممکن، از آنجایی که وجود دارد

N!

عناصر در

S_{N}

. با این حال، همانطور که به زودی خواهیم دید، تعداد مجموعه های متمایز

A (i_{1}, \dots, i_{N})

محدود شده است

O (N^{2})

. در واقع،

(†)

شامل (حداکثر)

\frac{N (N - 1)}{2}

نابرابری های خطی در a و b . این نابرابری ها را می توان به صورت نوشتاری نوشت

a (x_{i_{j}} - x_{i_{k}}) + b (y_{i_{j}} - y_{i_{k}}) \leq 0

1 \leq j < k \leq N

. بعضی از اینها

\frac{N (N - 1)}{2}

ممکن است منطبق باشند، یعنی زمانی که در مجموعه اصلی P ، جفت نقاطی وجود داشته باشند که پاره خط های موازی را تشکیل می دهند. از نظر هندسی، این نابرابری ها را تقسیم می کنند

(a, b)

هواپیما در (حداکثر)

N (N - 1)

کلاس های پارتیشن تعیین شده توسط خطوط

a (x_{i_{j}} - x_{i_{k}}) + b (y_{i_{j}} - y_{i_{k}}) = 0

، برای

1 \leq j < k \leq N

. این خطوط همه از منشاء می گذرد

(a, b)

هواپیما، و تعیین حداکثر

N (N - 1)

(نامحدود) نیم خط. این نیم خطوط هواپیما را بیشتر به داخل تقسیم می کنند

N (N - 1)

(نامحدود) برش های پای شکل .

متذکر می شویم که در نظر گرفتن مبدأ بی معنی است

(0, 0)

از

(a, b)

-plane، زیرا هیچ خطی با این نقطه مطابقت ندارد.

ما این را با استفاده از دو مثال افزایش پیچیدگی نشان می دهیم.

مثال 2.

ابتدا می گیریم $N = 3$ و نقاط P هستند $(x_{1}, y_{1}) = (0, 0)$ ، $(x_{2}, y_{2}) = (0, 1)$ و $(x_{3}, y_{3}) = (1, 0)$ . جدول زیر شش ترتیب احتمالی مجموعه شاخص را نشان می دهد ${1, 2, 3}$ و معادلات مربوطه که مجموعه ها را توصیف می کنند $A (i_{1}, i_{2}, i_{3})$ ، برای $(i_{1}, i_{2}, i_{3}) \in S_{3}$ .

$(i_{1}, i_{2}, i_{3})$	$A (i_{1}, i_{2}, i_{3})$
$(1, 2, 3)$	$0 \leq b \leq a$
$(1, 3, 2)$	$0 \leq a \leq b$
$(2, 1, 3)$	$b \leq 0 \leq a$
$(2, 3, 1)$	$b \leq a \leq 0$
$(3, 1, 2)$	$a \leq 0 \leq b$
$(3, 2, 1)$	$a \leq b \leq 0$

مجموعه ها

A (i_{1}, i_{2}, i_{3})

با خطوط مشخص می شوند

a = 0

b = 0

b = a

در

(a, b)

-سطح. این در شکل 2 نشان داده شده است . ما متذکر می شویم که مجموعه ها

A (i_{1}, i_{2}, i_{3})

از نظر توپولوژیکی بسته هستند و برخی از مجموعه ها

A (i_{1}, i_{2}, i_{3})

یک حاشیه را به اشتراک بگذارید که نیم خط است (همانطور که در شکل 2 مشاهده می شود ). مثلا،

A (1, 2, 3)

A (2, 1, 3)

محور a مثبت را به عنوان مرز به اشتراک بگذارید. برای تمام نقاط

(a, b)

با

a \geq 0

، ما سفارشات را داریم

(x_{1}, y_{1}) \leq (x_{2}, y_{2}) \leq (x_{3}, y_{3})

(x_{2}, y_{2}) \leq (x_{1}, y_{1}) \leq (x_{3}, y_{3})

، که مصادف هستند. در واقع،

a x_{1} \leq a x_{2} \leq a x_{3}

a x_{2} \leq a x_{1} \leq a x_{3}

هر دو مطابقت دارند

0 \leq 0 \leq a

برای

a > 0

در مثال قبلی، شش مجموعه داریم

A (i_{1}, i_{2}, i_{3})

. استثنایی، برای

N = 3

، ما داریم

N! = \frac{N (N - 1)}{2}

. این دیگر برای مقادیر بزرگتر N صادق نیست ، همانطور که مثال بعدی نشان می دهد.

در مثال 2 می بینیم که مجموعه مربوط به ترتیب است

1, 3, 2

و ترتیب معکوس آن

2, 3, 1

، برای مثال،

A (1, 3, 2)

A (2, 3, 1)

، بازتابی از یکدیگر در امتداد مبدأ هستند

(a, b)

-سطح. این برای همه صدق می کند

A (i_{1}, i_{2}, i_{3})

در مثال 2 (همانطور که با سایه های مربوط به زرد نشان داده شده است) و به طور کلی، همانطور که ویژگی زیر توضیح می دهد:

گزاره 1.

اگر

(i_{1}, . . ., i_{N}) \in S_{N}

، سپس

A (i_{N}, . . ., i_{1}) = {(a, b) ∣ (- a, - b) \in A (i_{1}, . . ., i_{N})}

اثبات

اجازه دهید

(i_{1}, . . ., i_{N}) \in S_{N}

. اگر

(a, b) \in A (i_{1}, . . ., i_{N})

، سپس

a x_{i_{1}} + b y_{i_{1}} \leq a x_{i_{2}} + b y_{i_{2}} \leq \dots \leq a x_{i_{N}} + b y_{i_{N}}

و بنابراین

- a x_{i_{1}} - b y_{i_{1}} \geq - a x_{i_{2}} - b y_{i_{2}} \geq \dots \geq - a x_{i_{N}} - b y_{i_{N}}

، که دلالت بر آن دارد

(- a, - b) \in A (i_{N}, . . ., i_{1})

. این یک شمول را ثابت می کند. شمول دیگر نیز همین برهان را دارد. ☐

مثال بعدی پیچیده تر، یک امتیاز به مجموعه P از مثال 2 اضافه می کند.

مثال 3.

در حال حاضر، ما می گیریم $N = 4$ و نقاط P هستند $(x_{1}, y_{1}) = (0, 0)$ ، $(x_{2}, y_{2}) = (0, 1)$ ، $(x_{3}, y_{3}) = (1, 0)$ و $(x_{4}, y_{4}) = (2, 1)$ . خاصیت 1 نشان می دهد که ما فقط باید 12 مورد را در نظر بگیریم $4! = 24$ جایگشت های مجموعه ${1, 2, 3, 4}$ . جدول زیر این 12 ترتیب مجموعه شاخص را نشان می دهد ${1, 2, 3, 4}$ و معادلات مربوطه که مجموعه ها را توصیف می کنند $A (i_{1}, i_{2}, i_{3}, i_{4})$ .

$(i_{1}, i_{2}, i_{3}, i_{4})$	$A (i_{1}, i_{2}, i_{3}, i_{4})$
$(1, 2, 3, 4)$	$0 \leq b \leq a \leq 2 a + b$
$(1, 2, 4, 3)$	$0 \leq b \leq 2 a + b \leq a$
$(1, 3, 2, 4)$	$0 \leq a \leq b \leq 2 a + b$
$(1, 3, 4, 2)$	$0 \leq a \leq 2 a + b \leq b \to a = 0 \leq b$
$(1, 4, 2, 3)$	$0 \leq 2 a + b \leq b \leq a$
$(1, 4, 3, 2)$	$0 \leq 2 a + b \leq a \leq b$
$(2, 1, 3, 4)$	$b \leq 0 \leq a \leq 2 a + b$
$(2, 1, 4, 3)$	$b \leq 0 \leq 2 a + b \leq a$
$(2, 3, 1, 4)$	$b \leq a \leq 0 \leq 2 a + b$
$(2, 4, 1, 3)$	$b \leq 2 a + b \leq 0 \leq a$
$(3, 1, 2, 4)$	$a \leq 0 \leq b \leq 2 a + b \to a = 0 \leq b$
$(3, 2, 1, 4)$	$a \leq b \leq 0 \leq 2 a + b$

از آنجا که خط از طریق

(x_{1}, y_{1}) = (0, 0)

(x_{3}, y_{3}) = (1, 0)

و خط از طریق

(x_{2}, y_{2}) = (0, 1)

(x_{4}, y_{4}) = (2, 1)

، کمتر از وجود دارد

\frac{4 (4 - 1)}{2} = 6

خطوط در

(a, b)

هواپیما که محدوده مجموعه

A (i_{1}, i_{2}, i_{3}, i_{4})

. در واقع، آنها پنج هستند:

a = 0

b = 0

b = a

b = - a

b = - 2 a

(همانطور که در جدول نیز مشاهده می شود). بنابراین، در اینجا

(a, b)

همانطور که در شکل 3 نشان داده شده است، صفحه به ده نیم خط و ده برش پای شکل تقسیم شده است . نیمی از برش ها نشان داده نشده اند، اما می توان آنها را از طریق Property 1 به دست آورد. همچنین در شکل 3 حقایقی نشان داده نشده است که

A (1, 3, 4, 2) = A (3, 1, 2, 4)

محور b غیر منفی است و آن

A (1, 2, 4, 3) = A (1, 4, 2, 3) = A (2, 3, 1, 4) = A (3, 2, 1, 4) = {(0, 0)}

که با هیچ خطی مطابقت ندارد. بنابراین، ما داریم

A (1, 3, 4, 2) = A (3, 1, 2, 4) \subset A (1, 2, 3, 4)

. این مشاهدات نشان می دهد که معمولا نه همه

4!

(یا

N!

) مجموعه ها به طور جداگانه رخ خواهند داد.

اکنون، ساخت ساختار داده را نشان می دهیم

L (P)

برای مثال های 2 و 3. ساختار

L (P)

در اصل یک درخت AVL است. درختان AVL که به نام های Adelson-Velsky و Landis [ 11 ] نامگذاری شده اند، درختان جستجوی دودویی هستند. این بدان معنی است که در هر یک از گره های آن، موارد با مقادیر کلید کمتر از گره در زیردرخت فرزند سمت چپ و مقادیر بزرگتر از مقدار کلید از گره در زیردرخت فرزند سمت راست ذخیره می شوند. درخت‌های جستجوی دودویی که m مقادیر کلیدی را ذخیره می‌کنند، در حالت ایده‌آل، امکان جستجوی یک مقدار کلیدی معین را در زمان می‌دهند.

O (\log m)

O (m)

، به جای

O (\log m)

روش درختی AVL به صورت پویا درخت AVL را پس از درج یا حذف گره ها با اعمال دنباله ای از چرخش ها یا چرخش های مضاعف متعادل می کند [ 11 ]. تعداد چرخش ها و دو چرخش های مورد نیاز برای متعادل کردن مجدد درخت در ارتفاع درخت خطی است. درخت‌های AVL «متعادل» باقی می‌مانند، به این معنا که برای هر گره، ارتفاع زیردرخت سمت چپ و زیردرخت سمت راست حداکثر یک تفاوت دارند. ارتفاع یک درخت را می توان به عنوان طول طولانی ترین مسیر از ریشه تا یک برگ تعریف کرد.

مثال 4.

دو مورد را در نظر می گیریم:

a \geq 0

a < 0

. توسط اموال 1، مورد

a < 0

را می توان به مورد تقلیل داد

a > 0

(با استفاده از ترتیب معکوس). بنابراین، اساسا، مورد

a \geq 0

، باید حل شود. فرض می کنیم

a \geq 0

. ابتدا شیب نیم خط هایی را که در نیم صفحه پیدا می کنیم مرتب می کنیم

a > 0

در محدوده

(- \infty, + \infty]

. در اینجا، ما موافق هستیم که محور b مثبت با معادله

a = 0

به صورت بیان می شود

b / a = + \infty

. در مثال 2، شیب ها را داریم

b / a = 0

b / a = 1

b / a = + \infty

، که دستور را می دهند

0 < 1 < + \infty

. ما از این شیب ها به عنوان مقادیر کلیدی برای ساختن درخت AVL استفاده می کنیم. برای مثال 2، این درخت در قسمت سمت چپ شکل 4 نشان داده شده است . ساختار داده مربوطه

L (P)

در قسمت سمت راست شکل 4 نشان داده شده است . برای این مثال، درخت AVL کاملا متعادل است. فواصل آبی زیر برگ درخت AVL نشان می دهد که کدام قسمت از فاصله است

(- \infty, + \infty]

مطابق با یک برگ در این مثال، دنباله‌ای از فواصل باز-بسته در برگ‌ها را داریم:

(- \infty, 0]

(0, - 1]

(1, + \infty]

{+ \infty}

. یک افزونگی کوچک برای پرونده وجود دارد

+ \infty

که توسط دو برگ پوشیده شده است. این فقط زمانی رخ می دهد که

b / a = + \infty

یک شیب است.

کادرهای قرمز رنگ در برگها ترتیب (شاخص) نقاط را نشان می دهد

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

، برای فاصله شیب ها در هر برگ. هر کادر قرمز نشان دهنده (یا حاوی) یک درخت جستجوی دودویی در ترتیب (یا جایگشت) موجود در آن است.

در مثال 3، دو شیب اضافی داریم، یعنی

b / a = - 2

b / a = - 1

. این دستور را می دهد

- 2 < 1 < 0 < 1 < + \infty

از دامنه ها اگر درج کنیم

- 2

- 1

در درخت AVL شکل 4 ، درخت AVL و ساختار را بدست می آوریم

L (P)

برای مثال 3، همانطور که در شکل 5 نشان داده شده است . در این مثال درخت AVL تقریبا متعادل است. ارتفاع زیردرخت سمت چپ ریشه یک بالاتر از زیردرخت سمت راست است.

ما خاطرنشان می کنیم که ارتفاع AVL از نظر تعداد گره های آن لگاریتمی است. از آنجایی که حداکثر وجود دارد

\frac{N (N - 1)}{2}

دامنه ها، ارتفاع داریم

O (\log \frac{N (N - 1)}{2}) = O (\log N)

. بنابراین، ما نیاز داریم

O (\log N)

زمان برای یافتن برگ مربوط به شیب یک خط معین.

اکنون قسمت پایینی سازه را توضیح می دهیم

L (P)

که با کادرهای قرمز رنگ در شکل 4 و شکل 5 نشان داده شده است . برای تعیین جایگشت سمت چپ، یک را انتخاب می کنیم

a > 0

و ب طوری که

\frac{b}{a}

به شدت کوچکتر از شیب اول است

- 2

. به عنوان مثال، ما می توانیم

b = - 3

a = 1

و توجه داشته باشید که هر انتخاب دیگری به گونه ای که

\frac{b}{a} < - 2

همان جایگشت را خواهد داد. بعد باید سفارش بدیم

a x_{i} + b y_{i}

، برای

(x_{i}, y_{i}) \in P

، برای

b = - 3

a = 1

. این ترتیب (یا جایگشت) را می دهد

(2, 1, 4, 3)

. برای برگه بعدی سمت راست این برگه سمت چپ، نیازی به انجام مجدد فرآیند کامل سفارش نداریم. فقط امتیاز

(x_{i}, y_{i})

(x_{j}, y_{j})

برای کدام

- 2 = - \frac{x_{i} - x_{j}}{y_{i} - y_{j}}

می تواند هنگام عبور از شیب ترتیب را تغییر دهد

- 2

. در این مثال می بینیم که شیب

- 2

ناشی از

(x_{1}, y_{1}) = (0, 0)

(x_{4}, y_{4}) = (2, 1)

و در واقع، جای سوئیچ 1 و 4 در جایگشت

(2, 1, 4, 3)

دادن

(2, 4, 1, 3)

برای برگ بعدی ما یادآوری می کنیم که اطلاعات جایگشت در “جعبه های قرمز” را می توان در خود درخت AVL باینری ذخیره کرد.

اکنون می توان از درخت جستجوی شکل 5 برای پاسخ به پرسش محدوده نیم صفحه استفاده کرد. به عنوان مثال، اگر خط ℓ با معادله

2 x - 3 y + 1 = 0

داده می شود، جایگشت را پیدا می کنیم

(2, 1, 4, 3)

در برگ که با فاصله مطابقت دارد

(- 2, - 1]

که در آن شیب

\frac{- 3}{2}

واقع شده است. برای دیدن کدام یک از

(x_{2}, y_{2}) = (0, 1)

(x_{1}, y_{1}) = (0, 0)

(x_{4}, y_{4}) = (2, 1)

(x_{3}, y_{3}) = (1, 0)

زیر ℓ هستند، ما محاسبه می کنیم

2 x_{i} - 3 y_{i}

برای

i = 2, 1, 4, 3

(به ترتیب) تا زمانی که این مقدار کاملاً پایین باشد

- c = - 1

. در این مورد فقط

(x_{2}, y_{2}) = (0, 1)

زیر ℓ یافت می شود.

اکنون قضیه زیر را نشان می‌دهیم که مثال‌های 2، 3 و 4 را تعمیم می‌دهد.

قضیه 2.

یک مجموعه داده شده است

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

از N نقطه در

R^{2}

، یک ساختار داده

L (P)

از اندازه

O (N^{3})

می تواند در زمان ساخته شود

O (N^{3})

به طوری که برای هر خط ورودی ℓ در

R^{2}

، توسط یک معادله داده می شود

a x + b y + c = 0

، امکان تعیین از

L (P)

که در

O (\log N)

زمانی که کدام یک از نقاط N در زیر، بالا و روی خط ℓ قرار دارند.

ساختار داده را می توان به روز کرد

O (N^{2} \log N)

زمانی که نقطه ای به P اضافه می شود یا از P حذف می شود.

قبل از اینکه این قضیه را اثبات کنیم، متذکر می شویم که پیچیدگی تعیین از

L (P)

، که از N نقطه ها در زیر، بالا و روی خط ℓ قرار دارند

O (\log N)

زمان. این شامل نوشتن پاسخ در مواقع ضروری نمی شود. بدیهی است که نوشتن این ترتیب لزوما ممکن است زمان خطی داشته باشد. با این حال، اگر به پاسخ اجازه داده شود که یک اشاره گر در درخت جستجو باشد و پاسخ واقعی شامل «همه نکاتی که قبل از این نقطه هستند» باشد، فهرست کردن مؤثر این نکات ممکن است ضروری نباشد. این امکان پذیر است زیرا جایگشت نقاط خود را می توان در یک درخت باینری (AVL) قرار داد. حال به اثبات قضیه می پردازیم.

اثبات

یک مجموعه داده شده است

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

از N نقطه در

R^{2}

، ابتدا شیب های موجود در را تعیین می کنیم

(a, b)

-صفحه خطوط

a (x_{i} - x_{j}) + b (y_{i} - y_{j}) = 0

، برای

1 \leq i < j \leq N

. حداکثر وجود دارد

\frac{N (N - 1)}{2}

چنین شیب هایی، که برخی ممکن است همزمان باشند. این طول می کشد

O (N^{2})

زمان و فضا.

اکنون، همانطور که در مثال 4 نشان دادیم، روی نیم صفحه تمرکز می کنیم که توسط

a \geq 0

. برای رسیدگی به پرونده

a < 0

می توانیم از Property 1 استفاده کنیم. در این مرحله می توانیم قسمت بالایی را بسازیم

L (P)

با ساختن یک درخت AVL روی شیب ها (به روشی که در مثال 4 نشان داده ایم). از آنجایی که هزینه درج یک گره در درخت AVL با n گره است

O (\log n)

، هزینه ساخت یک درخت AVL از n گره، با قرار دادن این n گره پشت سر هم، برابر است با

O (n \log n)

و درخت می گیرد

O (n)

فضا. اعمال شده به تنظیمات ما، ما حداکثر

\frac{N (N - 1)}{2}

شیب ها، بنابراین ساختن درخت AVL در این شیب ها طول می کشد

O (N^{2} \log N)

زمان و

O (N^{2})

فضا. اگر به برگ های درخت از چپ به راست نگاه کنیم، ساختن درخت AVL، به عنوان یک اثر جانبی، نظم شیب ها را ایجاد می کند. به این ترتیب، اطلاعات بازه‌ای را نیز بدست می‌آوریم که با فواصل آبی در شکل 4 و شکل 5 ارائه شده است .

پس از ساخته شدن درخت AVL، باید ترتیب (شاخص های) نقاط P را در هر یک از برگ های درخت تعیین کنیم. این ترتیبات با جایگشت در “جعبه های قرمز” در شکل 4 و شکل 5 نشان داده شده اند . بگذارید شیب هایی که در درخت AVL رخ می دهد باشد $s_{1}, s_{2}, . . ., s_{k}$ ، با $- \infty < s_{1} < s_{2} < \dots < s_{k} \leq + \infty .$ با گرفتن برخی از خودسرانه $a > 0$ و ب طوری که $- \infty < \frac{b}{a} < s_{1}$ و سفارش دادن $a x_{i} + b y_{i}$ ، برای $i = 1, . . ., N$ ، جایگشتی را بدست می آوریم که در سمت چپ ترین برگ درخت AVL است. ما می توانیم این جایگشت (در کادر قرمز) را به عنوان خود درخت AVL ذخیره کنیم. طول می کشد $O (N \log N)$ زمان و $O (N)$ فضایی برای ساخت این درخت AVL کوچکتر برای ذخیره سفارش. برای برگ‌های بعدی (از چپ به راست در درخت می‌رویم)، همانطور که از مقداری شیب عبور می‌کنیم $s_{ℓ}$ ، فقط ترتیب شاخص های i و j در مقایسه با برگ قبلی، اگر

س ℓ = - ایکس من - ایکس j y من - y j .

در واقع اگر، برای مثال

a x_{i} + b y_{i} \leq a x_{j} + b y_{j}

برای

\frac{b}{a} < s_{ℓ}

، پس داریم

a^{'} x_{j} + b^{'} y_{j} \leq a^{'} x_{i} + b^{'} y_{i}

برای

s_{ℓ} < \frac{b^{'}}{a^{'}}

. این بدان معناست که با رفتن از چپ به راست از میان برگ‌های درخت AVL، می‌توانیم جایگشت‌ها را در زمان خطی در N به‌روزرسانی کنیم. به‌روزرسانی کنیم .

از آنجایی که درخت AVL دارد

O (N^{2})

برگ، کل زمان ساخت سازه

L (P)

است

O (N^{2} \log N) + O (N \log N) + O (N^{2} \cdot N) = O (N^{3})

. ما همان فضای محدود را داریم. اشاره می کنیم که ارتفاع کل سازه

L (P)

که به دست می آوریم است

O (\log N^{2}) + O (\log N) = O (\log N)

پیچیدگی زمان پرس و جو به شرح زیر است. در خط ورودی ℓ که توسط معادله داده می شود

a x + b y + c = 0

، طول می کشد

O (\log N)

زمان تعیین برگ درخت AVL که شامل فاصله زمانی شیب است

\frac{b}{a}

واقع شده است. در واقع، ارتفاع درخت AVL از نظر تعداد گره های آن لگاریتمی است که

O (N^{2})

. اجازه دهید فرض کنیم که این برگ حاوی جایگشت است

(i_{1}, i_{2}, . . ., i_{N})

(در جعبه قرمزش). برای خروجی نقاطی که در زیر ℓ هستند ، می نویسیم

(x_{i_{j}}, y_{i_{j}})

به خروجی برای

j = 1, 2, . . .

تا زمانیکه

a x_{i_{j}} + b y_{i_{j}} < - c

. در حالت بدتر، خروجی شامل تمام نقاط P است . بدیهی است که این فرآیند نوشتن در اندازه خروجی زمان خطی می برد.

در نهایت، در مورد به روز رسانی درخت AVL زمانی که یک نقطه به P اضافه می شود یا یک نقطه از P حذف می شود، بحث می کنیم . افزودن یا حذف یک نقطه می تواند باعث معرفی یا حذف حداکثر N شیب شود. افزودن یا حذف N شیب در درخت AVL طول می کشد

O (N \log N)

زمان. در نهایت، جایگشت ها در برگ ها باید به روز شوند. یادآور می‌شویم که از آنجایی که فهرست‌های جایگشت خود به‌عنوان درخت‌های AVL ذخیره می‌شوند، پس حذف یک نقطه از P منجر به حذف یک برگ از درخت AVL در کادرهای قرمز می‌شود. به طور مشابه، افزودن یک نقطه به P منجر به افزودن یک برگ به درختان کوچک AVL می شود. این هزینه به روز رسانی دارد

O (\log N)

. بنابراین کل زمان به روز رسانی است

O (N^{2} \log N) .

این اثبات را به پایان می رساند. ☐

4. نزدیکترین نقطه به یک پرس و جو خط

قضیه 3.

یک مجموعه داده شده است

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

از N نقطه در

R^{2}

، یک ساختار داده

\bar{L} (P)

از اندازه

O (N^{3})

می تواند در زمان ساخته شود

O (N^{3})

به طوری که برای هر خط ورودی ℓ در

R^{2}

، توسط یک معادله داده می شود

a x + b y + c = 0

، می توان تعیین کرد، از

\bar{L} (P)

که در

O (\log N)

زمان، کدام یک از N نقطه P نزدیکترین (یا دورتر از) خط ℓ است.

اثبات

اگر هر خطی به ما داده شود که توسط معادله توصیف شده است $a x + b y + c = 0$ و نکته $(x_{0}, y_{0}) \in R^{2}$ ، سپس کوتاهترین فاصله بین آن خط و نقطه با عبارت داده می شود

∣ الف ایکس 0 + ب y 0 + ج ∣ آ 2 + ب 2 ——\sqrt .

بنابراین، تکنیک ها و ساختار داده شرح داده شده در بخش 3 را می توان برای پیش محاسبه برای یک مجموعه معین تنظیم کرد.

P = {(x_{i}, y_{i}) ∣ i = 1, \dots, N}

از N نقطه در

R^{2}

یک ساختار داده

\bar{L} (P)

از اندازه

O (N^{3})

به خصوص،

\bar{L} (P)

را می توان در زمان محاسبه کرد

O (N^{3})

به طوری که برای هر خط معین ℓ در

R^{2}

با معادله

a x + b y + c = 0,

می توان از آن تعیین کرد

\bar{L} (P)

که در

O (\log N)

زمان اینکه کدام یک از نقاط N به خط ℓ نزدیکتر است . در حقیقت،

\bar{L} (P)

فقط یک اصلاح جزئی از

L (P)

. به عنوان مثال، برای یافتن نزدیکترین نقطه به ℓ ، از آن استفاده می کنیم

L (P)

برای پیدا کردن اولین نقطه از P که زیر ℓ و اولین نقطه P که بالای ℓ است . ترتیب در درختان ردیف پایین تر از

L (P)

می تواند برای این مورد استفاده شود. سپس تصمیم می گیریم که کدام یک از این دو نقطه به ℓ نزدیکتر است و نتیجه نزدیکترین نقطه P به ℓ است. است .

برای یافتن دورترین نقطه P از ℓ ، دوباره استفاده می کنیم

L (P)

و به نقطه شروع و پایان ترتیبی که در ردیف بالایی پیدا می کنیم نگاه کنید

L (P)

. باز هم تصمیم می گیریم که کدام یک از این دو دورتر است و این نکته را به عنوان پاسخ برمی گردانیم. ☐

یافتن نزدیکترین فاصله هر نقطه در P به ℓ نیز برای یافتن دقیق تعداد نقاط زیر ℓ مفید است .

نتیجه 2.

اجازه دهید $d_{m i n}$ نزدیکترین فاصله هر نقطه در P به ℓ باشد. فرض کنید θ شیب ℓ باشد. سپس، $# A p p r o x (ℓ, P) = # B e l o w (ℓ, P)$ برای هرچی

m > max (sin θ ایکس حداکثر - ایکس دقیقه د دقیقه ، cos θ y حداکثر - y دقیقه د دقیقه) .

اثبات

واضح است که الگوریتم تقریب در بخش 2 در صورتی دقیق است که ارتفاع مثلث های اضافی کران پایین و کران بالایی کمتر از $d_{\min}$ زیرا در این صورت این مثلث های اضافی حاوی هیچ نقطه ای از P نیستند . همانطور که در شکل 6 نشان داده شده است ، اگر هر مثلث دارای طول a در امتداد محور x باشد، این حد ارتفاع را می توان تضمین کرد. $a < \frac{d_{\min}}{\sin θ}$ و ارتفاع b در امتداد محور y با $b < \frac{d_{\min}}{\cos θ}$ . ما آن را میدانیم

m = ایکس حداکثر - ایکس دقیقه آ

m = y حداکثر - y دقیقه ب .

شرط سابق و $a < \frac{d_{\min}}{\sin θ}$ دلالت بر آن دارد

m > sin θ ایکس حداکثر - ایکس دقیقه د دقیقه .

به همین ترتیب، شرط دوم و $b < \frac{d_{\min}}{\cos θ}$ دلالت بر آن دارد

m > cos θ y حداکثر - y دقیقه د دقیقه .

در نهایت، دو نابرابری نمایش داده شده آخر بر شرط قضیه دلالت دارند. ☐

5. نتیجه گیری ها

یک مشکل باز این است که تعیین کنیم آیا تکنیک های توصیف شده در بخش 2 و بخش 3 را می توان به بعد دلخواه d تعمیم داد . می توان مشاهده کرد که، برای N نقطه داده شده در ابعاد d ، شکل

(a_{1}, \dots, a_{d})

، ما خواهیم داشت

\frac{N (N - 1)}{2}

ابرصفحه های فرم

a_{1} x_{1} + \dots + a_{d} x_{d} + c = 0

که تقسیم می کند

R^{d}

حداکثر در

2^{d - 1} N

بخش ها با این حال، ساخت ساختار داده باید برای جستجوی موثر این بخش ها گسترش یابد.

همانطور که در مقدمه اشاره کردیم، تخمین انتخاب در مورد نقاط متحرک به معنای مشکل یافتن تعداد نقاط متحرکی است که در یک منطقه در یک زمان مشخص t . در مقابل، مشکل MaxCount می‌خواهد حداکثر تعداد نقاط متحرکی را که تا به حال در یک منطقه مشخص هستند و همچنین زمانی که حداکثر رخ می‌دهد، تخمین بزند. مشکل MaxCount در موردی که ناحیه مستطیلی است توسط اندرسون و ریوز [ 8 ] بررسی شد. زمانی که ناحیه در نظر گرفته شده ناحیه زیر یک خط باشد، یافتن MaxCount همچنان یک مشکل باز است.

منابع

دی برگ، ام. چئونگ، او. ون کرولد، ام. Overmars, M. Computational Geometry: Algorithms and Applications , 3rd ed.; Springer: برلین، آلمان، 2008. [ Google Scholar ]
پاچ، جی. آگاروال، هندسه ترکیبی PK ; جان وایلی و پسران: هوبوکن، نیوجرسی، ایالات متحده آمریکا، 1995. [ Google Scholar ]
Preparata، FP; Shamos, MI Computational Geometry: An Introduction ; Springer: برلین، آلمان، 1985. [ Google Scholar ]
Revesz, PZ مقدمه ای بر پایگاه های داده: از بیولوژیکی تا فضایی-زمانی ; Springer: برلین، آلمان، 2010. [ Google Scholar ]
Samet, H. مبانی ساختارهای داده چند بعدی و متریک ; مورگان کافمن: برلینگتون، MA، ایالات متحده آمریکا، 2006. [ Google Scholar ]
گوتینگ، آر. Schneider, M. Moving Object Databases ; Morgan Kaufmann: Burlington، MA، USA، 2005. [ Google Scholar ]
ریگو، پی. شول، ام. Agnés, V. Introduction to Spatial Databases: Applications to GIS ; Morgan Kaufmann: Burlington، MA، USA، 2002. [ Google Scholar ]
اندرسون، اس. Revesz، PZ Efficient MaxCount و عملگرهای آستانه اجسام متحرک. Geoinformatica 2009 ، 13 ، 355-396. [ Google Scholar ] [ CrossRef ]
چوی، YJ; Chung, CW تخمین گزینش پذیری برای پرس و جوهای مکانی-زمانی به اجسام متحرک. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 2002 در مدیریت داده ها، مدیسون، WI، ایالات متحده آمریکا، 4 تا 6 ژوئن 2002. ACM Press: نیویورک، نیویورک، ایالات متحده آمریکا، 2002; صص 440-451. [ Google Scholar ]
سان، ج. تائو، ی. پاپادیاس، دی. Kollios، G. انتخابی پیوستن فضایی-زمانی. Inf. سیستم 2006 ، 31 ، 793-813. [ Google Scholar ] [ CrossRef ]
ادلسون-ولسکی، جی. Landis, E. الگوریتمی برای سازماندهی اطلاعات. ریاضی شوروی Doklady 1962 ، 3 ، 1259-1263. [ Google Scholar ]
اوبه، RO; Hsu، LS PostGIS در عمل ؛ انتشارات منینگ: جزیره پناهگاه، نیویورک، ایالات متحده آمریکا، 2011. [ Google Scholar ]
پری، م. استرادا، ا. داس، اس. Banerjee, J. توسعه برنامه های GeoSPARQL با Oracle Spatial و Graph. در مجموعه مقالات اولین کارگاه بین المللی مشترک در مورد شبکه های حسگر معنایی و Terra Cognita (SSN-TC 2015) و چهارمین کارگاه بین المللی ترتیب و استدلال (OrdRing 2015) که با چهاردهمین کنفرانس بین المللی وب معنایی (ISWC 2015) برگزار شد. , PA, USA, 11–12 اکتبر 2015; Kyzirakos، K.، Henson، CA، Perry، M.، Varanka، D.، Grütter، R.، Calbimonte، J.، Celino، I.، Valle، ED، Dell’Aglio، D.، Krötzsch، M.، و همکاران، ویرایش. جلد 1488، ص 57–61.
ریوز، پی. کانجامالا، پ. لی، ی. لیو، ی. Wang, Y. سیستم پایگاه داده محدودیت MLPQ/GIS. در مجموعه مقالات کنفرانس بین المللی ACM-SIGMOD در مدیریت داده ها، دالاس، TX، ایالات متحده، 16-18 می 2000. ACM Press: نیویورک، نیویورک، ایالات متحده آمریکا، 2000; پ. 601. [ Google Scholar ]
شازل، بی. گیباس، ال. لی، دی. قدرت دوگانگی هندسی. BIT 1985 ، 25 ، 76-90. [ Google Scholar ] [ CrossRef ]
Xiao, N. الگوریتم های GIS ; SAGE Publishing: New York, NY, USA, 2015. [ Google Scholar ]
Revesz، PZ الگوریتم های نمایه سازی مستطیل کارآمد بر اساس تسلط نقطه. در مجموعه مقالات دوازدهمین سمپوزیوم بین المللی در بازنمایی و استدلال زمانی، برلینگتون، VT، ایالات متحده، 23-25 ژوئن 2005. ص 210-212.
درختان جستجوی چند بعدی باینری Bentley، JL که برای جستجوی انجمنی استفاده می شود. اشتراک. ACM 1975 ، 18 ، 509-517. [ Google Scholar ] [ CrossRef ]

شکل 1. تقریب نقاط زیر خط ℓ با

m = 4

شکل 2

(a, b)

– صفحه (به غیر از مرزهای مشترک) در شش برش پای شکل نامحدود (مجموعه ها) تقسیم شده است.

A (i_{1}, i_{2}, i_{3})

در سایه های مختلف زرد)، که توسط خطوط مشخص می شود

a = 0

b = 0

b = a

(به رنگ آبی).

شکل 3

(a, b)

-صفحه (جدا از مرزهای مشترک) در ده برش پای شکل نامحدود (مجموعه ها) تقسیم شده است.

A (i_{1}, i_{2}, i_{3}, i_{4})

در سایه های مختلف زرد)، که توسط خطوط مشخص می شود

a = 0

b = 0

b = a

b = - a

b = - 2 a

(به رنگ آبی). برش های بالای محور منفی a نشان داده نمی شوند، اما می توان از طریق Property 1 به دست آورد.

شکل 4. درخت AVL برای دامنه ها

0 < 1 < + \infty

( سمت چپ ) و ساختار مربوطه

L (P)

( سمت راست ) برای مجموعه P از مثال 2. فواصل آبی نشان دهنده مجموعه شیب پوشیده شده توسط یک برگ است.

شکل 5. درخت AVL برای دامنه ها

- 2 < - 1 < 0 < 1 < + \infty

( سمت چپ ) و ساختار مربوطه

L (P)

( سمت راست ) برای مجموعه P از مثال 3. فواصل آبی رنگ مجموعه شیب پوشیده شده توسط یک برگ را نشان می دهد.

شکل 6. نمای جزئی از یک تقسیم که زیر ℓ مثلث با

d_{\min}

ارتفاع و اضلاع a و b به ترتیب موازی با محور x – و y – هستند.

© 2017 توسط نویسندگان. دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC BY) ( http://creativecommons.org/licenses/by/4.0/ ) توزیع شده است

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

1.1. بیان مشکل و بررسی اجمالی نتایج

1.2. سناریوهای کاربردی

1.3. کار مرتبط

2. تقریب تعداد نقاط زیر یک خط

3. یک جستجوی موقعیت مکانی با توجه به یک خط

4. نزدیکترین نقطه به یک پرس و جو خط

5. نتیجه گیری ها

منابع

قبلیارزیابی اثربخشی و پوشش فضایی شبکه های حمل و نقل عمومی در مقاصد گردشگری مبتنی بر GIS

بعدیارزیابی سلامت اکوسیستم تالاب در حوضه رودخانه یانگ تسه و آمازون

بدون نظر

دیدگاهتان را بنویسید لغو پاسخ