I n d on e s i an   Jo u r n al   o f  El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   15 ,   N o .   3 ,  S e pt e m b e r   2 01 9 ,   pp .   1629 ~ 1636   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 5 .i 3 . pp 162 9 - 1636             1629       Jou r n al   h o m e pa ge :  ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   M o d i f i e d   b r u t e   f o r c e   a l g o r i t h m   t o   s o l v e   t h e   c l o sest p a i r   o f   p o i n t s  p r o b l e m   b a sed  o n   d y n a m i c   w a r p i n g       R h o w e l   M .   D e l l o s a 1 ,  A r n e l   C .   F aja r d o 2 ,  R u ji   P .   M e d i n a 3   1 , 3 G r a dua t e   S c ho o l ,   T e c hno l o g i c a l   I ns t i t u t e   o f   t h e   P hi l i ppi ne s   Q u e z o n  C i t y ,   P h i l i pp i n e s   2 S c hoo l   o f   E ng i ne e r i ng   a n d  I nf o r m a t i o n  T e c hno l o gy ,   M a nu e l   L .   Q u e z o n  U ni v e r s i t y ,   P h i l i pp i n e s       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e d  O c t   1,   2018   R e v i s e d  D e c   10,   2018   A c c e pt e d  J an   25,   201 9       T hi s   pa pe r   i nt r o duc e s   a n   a l g o r i t hm   t o   s o l v e   t he   c l o s e s t   pa i r   o f   po i nt s   p r o bl e m   i n  a   2D   p l a n e   b a s e d  o n  dy na m i c   w a r pi ng .   T he   a l g o r i t hm   c o m put e s   a l l   t he   di s t a nc e s   be t w e e n  t he   s e t   o f   po i nt s   P ( x ,   y )   a nd  a   r e f e r e nc e   po i nt   R ( i ,   j ) ,   r e c o r ds   a l l   t he   r e s u l t   i n   a   g r i d  a nd   f i na l l y   de t e r m i ne s   t he   m i n i m u m   di s t a nc e   us i ng   s c he m a t i c   s t e ps .   R e s u l t s   s ho w   t ha t   t h e   a l g o r i t hm   o f   f i ndi ng   t he   c l o s e s t   pa i r   o f   po i nt s   h a s   a c h i e v e d  l e s s   num b e r   o f   c om pa r i s o ns   i n  de t e r m i ni ng   t he   c l o s e s t   p a i r   o f   po i nt s   c o m pa r e d  w i t h  t he   b r u t e   f o r c e   a nd  d i v i de - a n d - c o nque r   m e t ho ds   o f   t he   c l o s e s t   pa i r   o f   po i nt s .     Ke y w or ds :   B r ut e   f o r c e   Cl o s e s t   p a i r  o f   p o i n t s     D i v i de - a nd - c o n que r   D y n a m i c   w a rpi n g   P o s i t i o n   e s t i m a t i o n   C opy r i gh t   ©   201 9   I n s t i t ut e   o f   A dv anc e d  E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   R h ow e l   M .   D e l l o s a ,     G ra dua t e   S c h o o l ,     T e c hn o l o gi c a l   I n s t i t ut e   o f   t h e   P h i l i p pi n e s - Q ue z o n  Ci t y ,     938  A u r o r a   B o ul e v a r d ,   Cub a o ,   Q ue z o n  Ci t y ,  P hi l i ppi n e s .   E m a i l :   rh o w e l de l l o s a @ a s i a t e c h. e du. p h       1.   I N TR O D U C TI O N     T h e   de t e rm i na t i o n   o f   t h e   c l o s e s t   pa i r   o f   po i n t s   (CP P )  i n   a   t w o - di m e n s i o n a l   pl a n e   i s   o n e   o f   t h e   b a s i c   pr o b l e m s   of   c o m put a t i o n a l   ge o m e t r y .   S i m i l a r i t y   m a t c hi n g ,   p a t t e rn   r e c o gn i t i o n,   c o m put e r   v i s i o n   a n d  po s i t i o n   e s t i m a t i o n   a r e   s o m e   of   t h e   a ppl i c a t i o n s   of   CP P   [1 ]  a n d  [ 2 ].   O n e   of   t h e   t y pi c a l   a pp r o a c h e s   t o   s o l v i n g  t h e   pr o b l e m   o n   t h e   c l o s e s t   pa i r   o f   p o i n t s   i s   t h e   b r ut e   fo r c e   m e t ho d.   In   t hi s   m e t h o d,   t h e   c o m put a t i o n   o f  di s t a n c e s   of   a l l   pa i r s   o f   po i n t s   i s   n e c e s s a r y   t o   f i n d  o ut   t h e   c l o s e s t   pa i r.   T o   c o m put e   f o r   t h e   t o t a l   n u m b e r   o f   c o m pa r i s o n s   of   b r ut e   f o r c e   m e t h o d,   e qua t i o n   ( 1)  w a s   us e d.      = ( − 1 ) 2     (1)     w h e r e :     TC     -   T h e   n um b e r  o f   c o m pa r i s o n s   n    -   T o t a l   num b e r  o f   di s t a n c e   t o   b e   c o m pa r e d.     T h e   di v i de - a n d - c o n q ue r   a l go r i t hm   w a s   us e d  t o   i m p r o v e   t he   b r ut e   f o r c e   m e t h o d.   T h e   s t udy   of   [ 3 ]  us e d  t hi s   a pp r o a c h   t o   s o l ve   t h e   c l o s e s t   pa i r   p r o b l e m   i n   a   2 - d i m e n s i o na l   pl a n e .   I t   u t i l i z e d  t h e   c o n c e pt   i n t r o duc e d  by   [ 4 ]  o n   t h e   c l o s e s t   pa i r   o f   po i n t s   p r o b l e m   a nd  m o di f i e d  t h e   d i v i de - a n d - c o n que r   a l go ri t hm   by   c o m put i n g  a t   l e a s t   s e v e n   pa i r w i s e   c o m pa r i s o n s   i n   t h e   c e n t ra l   s l a b .   A n o t h e r   e nha n c e m e nt   w a s   pr e s e n t e d  b y   [ 5 ]  w h e r e i n  a n  i m p r o v e d  v e r s i o n   o f   t h e   di v i de - a n d - c o n q ue r   a l go r i t h m   o n   t h e   pl a n a r  s e t   us e d  a t   m o s t   f o ur   pa i r w i s e   c o m pa r i s o n s   i n   t h e   c o m b i n i n g  s t e p  f o r   e a c h   po i nt   i n   t h e   c e n t r a l   s l a b .   I n   2006 ,   t h e   s t ud y   o f  [ 6 ]  s h o w e d   t ha t   t h e   di v i de - a nd - c o n que r   a l go r i t hm   p a i r w i s e   c o m pa ri s o n   i s   po s s i b l e   t o   b e   r e duc e d  i n   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   3 ,  S e pt e m b e r   2 019   :     1 6 2 9   -   1 6 3 6   1630   c o m b i n i ng  s t e p  i n   t h e   c e n t ra l   s l a b   f o r   t h e i r  e nha n c e d  v e r s i o n .   L a t e r ,   t h e   s t udy   of   [ 7 ]  p r e s e n t e d  a n o t h e r  e nh a n c e m e n t   o f   di v i de - a nd - c o n que r   a l go ri t hm   c a l l e d  t h e   B a s i c - 2  w h e r e   t w o   pa i r w i s e   c o m pa r i s o n s   w e r e   us e d   i n   t h e   c o m b i n i ng  s t e p   f o r   e a c h  po i n t   i n  t h e   c e n t ra l   l a b .   In  2015 ,   t h e   P a i r - P r u n e d_CP   a l go r i t h m   o f   [ 8 ]  w a s   i nt r o duc e d.   I t   i s   a   s i m pl e   a nd  e f f i c i e n t   a l go r i t hm   t o   s o l ve   t h e   c l os e s t   pa i r   o f   p o i n t s   p r o b l e m .   T h e   a l go r i t hm   fun c t i o na l i t i e s   fo c us e d  o n   t h e   c o m put a t i o n   o f  t h e   di s t a n c e s   o f   t h e   pa i r   o f   po i n t s   w hi c h  m a y   be   c l o s e r   t h a n  t h e   i n i t i a l   c l o s e s t   pa i r  o f   po i n t s .   It   i s   a   c o m pa r i s o n - b a s e d  de t e r m i ni s t i c   a p p r o a c h  t o   s o l v e   t h e   CP P   p r o b l e m .     D y n a m i c   w a r p i n g  (D W )  i s   a   dy n a m i c   p r o g r a m m i n g  t e c hn i que   us e d  t o   m a t c h   t h e   s e que n c e   f o r   a   s pe c i f i c   a ppl i c a t i o n.   S o m e   of   t h e   a ppl i c a t i o n s   o f  D W   i n c l ud e   t h e   undi r e c t e d  gra p h   m o de l   f o r   c a l i b r a t i n g  a n d  s t o r i n g   s e que n c e - t y p e   r a di o - m a p  w hi c h  r e duc e d  t h e   di s p a r i t i e s   of   RS S .   T h e   s t u dy   of   [ 9 ]  s h o w e d  a n  i n c r e a s e   i n   a c c ur a c y   of   20%  us i n g  d y n a m i c   w a r pi ng.   T h e   i n t e r e s t i n g  f e a t u r e   of   d y n a m i c   w a r pi n g  i s   i t s   h e u r i s t i c   a pp r o a c h   t o   pa t t e rn   s e a r c hi n g.   T h e   w a r p m a p  o f   [ 9 ]  i s   a n   a c c u r a t e   a n d  e f fi c i e n t   i ndo o r   l o c a l i z a t i o n   i n   s e que n c e   t y p e   r a di o   m a p.   T h e   ke y   fe a t u r e   of   t h i s   s t udy   w a s   t h e   c a pa b i l i t y   of   i t s   s y s t e m   o f  a c c ur a t e   a n d   e ff i c i e n t   po s i t i o n   e s t i m a t i o n .     A n o t h e r  CP P   a l go r i t hm   i s   t h e   s t udy   of   [10]  t ha t   m a ke s   us e   of   a n  a l go ri t hm   t o   s o l ve   t h e   c l o s e s t   pa i r  pr o b l e m   w i t h   t h e   a i d  o f   t h e   t r e e   m o de l .   It   w a s   a l s o   pr o v e n   by   t h e   s t udy   of   [11]  t h a t   w i t h   t h e   us e   of   a   di v i de - a n d - c o n que r   a pp r o a c h ,   t h e   c l o s e s t   pa i r   o f  po i n t   p r o b l e m   c a n   b e   i n i t i a l l y   s o l ve d  i n   m uc h   h i g h e r   d i m e n s i o n s   fo r   pl a na r   c a s e .   T h e   di v i de - a nd - c o n que r   a l go ri t hm   m a ke s   i t   po s s i b l e   t o   l e s s e n   t h e   n u m b e r  o f   c o m pa ri s o n s   w h i c h   c o n t ri b ut e   t o   t h e   e ff i c i e n c y   of   t h e   a pp r o a c h.   T h e   s t u d y   o f  [12]  t h e   di v i s i o n s   i n t o   s e ve r a l   num b e r s   o f  gr o ups   w e r e   c o n s i de r e d  i n  t h e i r   e xpe r i m e n t   t h a t   de c r e a s e s   t he   n u m b e r   o f   c o m pa ri s o n s .   I t   w a s   a l s o   p r o v e n   b y   [13]  a n d   [14]   us e d  p l a n e - s w e e p  a n d   o pt i m a l   a l go r i t hm   t o   s o l v e   t h e   c l o s e s t   pa i r  o f   po i n t ’s   p r o b l e m .   T h e   t h e o r y   be h i n d  [1 5,   16 ]  o n   t h e   c l o s e s t   pa i r   o f   po i n t s   pr o b l e m s   s o l ut i o n s   ha d  c o n s i de r e d  t h e   a ppl i c a t i o n   o f   s e ve r a l   a l go r i t h m s   t o   r e duc e   t h e   e xpe c t e d   r u nni n g   t i m e .   T h e s e   a l go ri t hm s   a r e   t h e   s a m e   a l go ri t hm   us e d  f o r   t h e   l o c a l i t y   s e n s i t i v e   ha s h i n g   [17 ],   l i g h t   b ul b   p r o b l e m   [18]  a n d   c o i n  f l i p  o f   R a b i n   [ 19].   O n e   o f   t h e   s i m i l a r   c l o s e s t   pa i r s   o f   po i n t ' s   p r o b l e m   i s   t h e   t i m e   s e r i e s   m o t i f   m i ni n g .   I t   i s   a n  a ppl i c a t i o n  of   CP P   i n   l a rge   di m e n s i o n a l   s pa c e   t ha t   n e e ds   t o   h a v e   a n   e ff i c i e n t   a n d   a c c ura t e   r e s ul t .   T h e   s t udy   of   [20]   pr e s e nt e d  t h e   f i r s t   e xa c t   m o t i f   s e a r c h   a l go r i t h m   f o r   t i m e   s e r i e s   m o t i f   m i ni n g  t ha t   o ut pe r f o r m e d  t h e   b r ut e - fo r c e   a l go r i t hm .   T hi s   a l go r i t hm   b e c a m e   t h e   b e s t   p e r f o r m i n g  a l go ri t hm   i n   p ra c t i c e   fo r   t i m e   s e r i e s   m o t i f  m i ni n g .   T h e   s a m e   pr o b l e m   w a s   a l s o   e xpl o r e d  by   s e ve r a l   s t udi e s   t ha t   us e d  pr o b a b i l i s t i c   a n d  a p p r o xi m a t e   a l go ri t hm s   f o r   s o l v i n g   t i m e   s e r i e s   m o t i f   m i ni n g .   T h e   s t udy   of   [21]  a ppl i e d  i t   t o   t h e   m o t i o n - m o t i f   g ra p h.   T h e   s t udy   of   [ 22]  e n ha n c e d  t h e   t i m e   s e ri e s   m o t i f s   us i n g  t h e   p r o b a b i l i s t i c   a l go r i t hm .   T h e   s t udy   of   [23]  e xpl o r e d  t h e   po s s i b i l i t y   of   a ppl i c a t i o n   o f   t i m e   s e r i e s   i n  k n o w l e dge   c o n s t r uc t i o n   us i n g  a   c o l l a b o r a t i v e   e xpl o r a t i o n   s y s t e m .   T h e   pa pe r  o f   [24]  a pp l i e d  i t   t o   h u m a n   m o t i o n   a n d   [2 5]  h a v e   t r i e d  t o   f i n d   o ut   t ha t   m u l t i v a ri a t e   M o t i f s   us i n g  s ub s e q ue n c e   de n s i t y   e s t i m a t i o n   a n d  g r e e dy   m i xt u r e   l e a rni n g  i s   po s s i b l e   a n d  us e f ul   f o r   t i m e   s e r i e s   m o t i f   m i ni n g  r e f e r e n c e .   B o t h  o f   t h e   p a pe r s   o f   [21]  a n d   [22]   a r e   c o n c e rn e d  o n   t h e   a ppl i c a t i o n   o f   t i m e   s e r i e s   m o t i f  m i ni n g   p r i n c i pl e   t o   m a c h i n e   l e a rni n g   w h e r e i n   a   l a r ge   s c a l e   t i m e   s e ri e s   da t a b a s e   a r e   p r o c e s s e d.     T a k i n g  a n   a c c o un t   o n   i t s   f un c t i o na l i t i e s   o n   t h e   n u m b e r   o f   c o m pa r i s o n s ,   t h e   b r ut e   f o r c e   m e t h o d  h a s   t h e   m o s t   n u m b e r   o f   c o m pa ri s o n s   o f   t h e   di s t a n c e s   w h i l e   t h e   di v i de - a n d - c o n que r   a l go ri t hm   h a s   r e duc e d  s uc h.   In  t h e   c a s e   o f   c oo r di n a t e - b a s e d  s i m i l a r i t y   de t e r m i na t i o n ,   t h e   c l o s e r   t h e   r e f e r e n c e   po i nt   t o   t h e   s e t   o f   po i n t s ,   t h e   m o r e   s i m i l a r  t h e   r e f e r e n c e   po i nt .     Co n s i de r   t h e   r e f e r e n c e   po i n t   R (i ,   j )  a n d   t h e   s e t   o f   p o i n t s   { A (x 1 ,   y 1 ),   B (x 2 ,   y 2 ),   C(x 3 ,   y 3 )  a nd  D (x 4 ,  y 4 )} .   T h e   b r ut e   fo r c e   m e t h o d  w i l l   f i n d  o ut   a l l   t h e   di s t a n c e s   of   t h e   r e f e r e n c e   po i n t   R (i ,   j )  f r o m   t h e   f i ve   p o i n t s   { R ,   A ,   B ,   C ,   D }   w hi c h  a c c um u l a t e s   10   di s t a n c e   c o m put a t i o n s   { R A ,   R B ,   R C,   R D ,   A B ,   A C,   A D ,   B C,   B D ,   CD }   a n d   de t e r m i n e   t h e   m i ni m um   di s t a n c e   t o   f i n d   o ut   t h e   c o r r e s po n di ng  c l o s e s t   po i n t   f r o m   t h e   r e f e r e n c e   po i n t .   T h e   di v i de - a n d - c o n q ue r   a l go r i t h m   w i l l   f i nd  o ut   t h e   num b e r   o f   p o s s i b l e   di v i s i o n s   a n d  c o m put e   f o r   t h e   di s t a n c e s   o f   e a c h   o f   t h e   di v i s i o n   o f   po i n t s .   A s   a   r e s ul t ,   t h e   num b e r   o f   c o m pa ri s o n s   b e t w e e n   t h e   di s t a n c e s     i s   r e duc e d.   In  t hi s   s t udy ,   a   n e w   a pp r o a c h   t o   s o l ve   t h e   CP P   p r o b l e m s   i s   pr e s e nt e d  w h e r e   t h e   dy n a m i c   w a rpi n g   i s   a ppl i e d  t o   m i ni m i z e   t h e   num b e r   o f   c o m pa r i s o n s   o f   di s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   R (i ,   j )  a n d  t h e   s e t   of  po i n t s   P (x n ,   y n ).   T h e   c o m put e d  di s t a n c e s   a r e   p r e s e n t e d  i n   c o o r di n a t e s - m a p   t o   b e   us e d  fo r   s i m i l a ri t y   de t e r m i n a t i o n .   T h e   n u m b e r s   of   c o m pa ri s o n s   of   t h e   pr o po s e d  a l go ri t hm   a r e   c o m pa r e d  w i t h   b r ut e   f o r c e   a n d  di v i de - a n d - c o n que r   m e t h o ds   of   CP P .   F ut ur e   a ppl i c a t i o ns   m a y   c o n s i de r   t h e   us e   of   r a di o   f r e que n c y   i de nt i f i c a t i o n   a n d   v i s i b l e   l i g ht   c o m m u n i c a t i o n  f o r   l o c a t i o n   e s t i m a t i o n  a s   s t ud i e d  by   [2 6 ].       2.   P R O P O S ED   A LG O R I T H M   T h e   p r o po s e d  m o di f i c a t i o n   o f   t h e   b r ut e   f o r c e   m e t h o d  o f   s ol v i n g   t h e   CP P   p r o b l e m   i s   p r e s e nt e d  by   i n t r o duc i n g  t h e   c o o r di n a t e s - m a p  g ri d .   A   c oo r di na t e s - m a p  g ri d  w i t h   16  s a m pl e   c e l l s   i s   i l l us t ra t e d  i n   F i gu r e   1.   F i gu r e   2   s h o w s   t h e   c o o r di n a t e s - m a p   g r i d.   E a c h  c e l l   o f   t he   c oo r di n a t e s - m a p   g r i d  i s   t h e   c o n t a i n e r   o f   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i     IS S N :   2502 - 4752       Modi f i e d  br u t e   f or c e   al gor i t hm   t o  s o l v e   t he   c l os e s t   pa i r   o f   po i nt s   pr obl e m   bas e d   on  . . . .   ( R how e l   M .   D e l l os a)   1631   di s t a n c e   b e t w e e n   t h e   r e f e r e n c e   po i n t   R ( i ,   j )  a n d  t h e   s e t   o f   p o i n t s   a s s i g n e d  t o   a   pa rt i c ul a r   c e l l .   F o r  e xa m pl e ,   t h e   D 11  c e l l   c o n t a i n s   t h e   di s t a n c e   b e t w e e n   t h e   r e f e r e n c e   po i nt   R (i ,   j )  a n d  t h e   c o o r di na t e s   P (1 ,   1)  a n d   D 12  c e l l   c o n t a i n s   t h e   di s t a n c e   b e t w e e n   t h e   r e f e r e n c e   po i n t   R (i ,   j )  a nd  t h e   c o o r di na t e s   P (1 ,   2) .         D 1 4   D 2 4   D 3 4   D 4 4   D 1 3   D 2 3   D 3 3   D 4 3   D 1 2   D 2 2   D 3 2   D 4 2   D 1 1   D 2 1   D 3 1   D 4 1     F i gu r e   1 .   Co o r di na t e s - m a p   G r i d       0 . 6   1 . 2   2 . 1   3 . 1   0 . 4   1 . 1   2 . 0   3 . 0   1 . 4   1 . 7   2 . 4   3 . 3   2 . 4   2 . 6   3 . 1   3 . 8     F i gu r e   2 .  S a m p l e   D i s t a n c e   O ut pu t   o f   Co o r di n a t e s - m a p   G r i d       2. 1 .       A l go r i th m   fo r   D i s t an c e   C o m p u tati o n   an d   S to r i n g  o f  D i s tan c e   i n   th e   C o o r d i n ate s - M ap   G r i d   In p ut     :   R e fe r e n c e   P o i nt   { R   ( i ,   j )}   a n d  t h e   s e t   o f   po i nt s   { (1 ,   1), . . (1,   4),   (2,   1) . . (2,   4) …(4, 1. . (4 ,   4)   }     O ut put   :   D i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   (R )  a nd  t h e   s e t   o f   po i nt s   (P )   i n  t h e   c oo r di na t e - m a p   g r i d       L oo p0:     F o r   x  = 1   t o   4       L oo p1:         F o r   y   =   1   t o   4           D xy   =   di s t a n c e   b e t w e e n   R (i ,   j )  a n d   P   ( x,   y )          i n c   y         S t o r e   D xy   i n  t h e   c oo r di na t e s - m a p   g ri d             i f   x< = 4   t h e n           G o t o   l oo p  1             E l s e             x= 1             i n c   y             G o t o   l oo p0     E n di f   E n d  f o r   E n d  f o r               S am p l e   o u tp u t:   In p ut     :   R e fe r e n c e   P o i nt   { R (1,   3 . 4)}   a nd  t h e   s e t   o f   po i n t s   { (1 ,   1 ), . . ( 1 ,   4) ,   (2 ,   1) . . (2,   4) …(4 , 1). . (4 ,   4)  }     O ut put   :   D i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   (R )  a nd  t h e   s e t   o f   po i nt s   (P )   i n  t h e   c oo r di na t e - m a p   g r i d     2. 2 .       S c h e m ati c   S t e p s   th at  D e t e r m i n e   th e   M i n i m u m   D i s tan c e   an d   th e   S e t   o f  P o i n t  P (X ,   Y )   C l o s e r   to  R e fe r e n c e   P o i n t  R (I ,   J)   In p ut     :   D i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   R (i ,   j )  a nd  P (x ,   y )  i n  t h e   c o o r di na t e s - m a p   g r i d.   O ut put   :   C l o s e s t   po i n t   P (x ,   y ).   1.   U s i n g  t h e   c o o r di n a t e s - m a p  g ri d  o f   F i gur e   1 ,   s t a r t   f r o m   t h e   uppe r   ri g ht   c o rn e r   o f   t h e   c o o r di n a t e s - m a p   g ri d  us i n g   t h e   s c h e m a t i c   s t e p  p r e s e nt e d  i n  F i g u r e   3 .             F i gu r e   3 .   T h e   s c h e m a t i c   s t e p   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   3 ,  S e pt e m b e r   2 019   :     1 6 2 9   -   1 6 3 6   1632   2.   F o l l ow   t h e   s c h e m a t i c   s t e p   o f   F i gur e   3.           F i gu r e   4 .   I l l us t r a t i o n  o f   t h e   s c h e m a t i c   s t e p  t o   t h e   c o o r di n a t e s - m a p   g ri d       3.   D e t e r m i n e   t h e   m i ni m um   v a l ue   o f   t h e   f o ur   c e l l s   (D 44,   D 34 ,   D 33,   a n d   D 43) .     4.   M ov e   t o   t h e   n e x t   s t e p  by   c o n s i de ri n g   t h e   m i ni m u m   d i s t a n c e   v a l ue   a s   t h e   “ S t a r t ”   o f   t h e   n e xt   s c h e m a t i c   s t e p .   (A s s um pt i o n :   D 34   i s   t h e   m i ni m um   v a l ue ).           F i gu r e   5 .  I l l us t r a t i o n  o f   t h e   n e xt   S c h e m a t i c   S t e p       5.   If   t h e   m i n i m u m   di s t a n c e   v a l ue   di d  n o t   c h a n ge   a n y m o r e ,   t h e   c o rr e s po n di n g  c o o r di n a t e s   of   t h e   m i ni m u m   di s t a n c e   a r e   t h e   c l o s e s t   c oo r di na t e s   o f   t h e   r e f e r e n c e   po i n t   R   (i ,   j ).     S am p l e   o u tp u t:   In p ut     :   D i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   R (1,   3. 4)   a n d  P ( x,   y )  di s pl a y e d  i n   t h e   c o o r di n a t e s - m a p   g r i d.   O ut put   :   C l o s e s t   po i n t   P (x ,   y ).   S te p s :           F i gu r e   6 .  F i r s t   S t e p         F i gu r e   7 .  S e c o n d  S t e p         F i gu r e   8 .  T h i rd  S t e p       F i gu r e   9 .  S u m m a r y   of   S t e ps   P r o c e s s       O u tp u t:  P (x,   y )  =   P   (1,   3 ).   T h e r e f o r e ,   t h e   r e f e r e n c e   po i nt s   R   (1,   3. 4)  a nd  P   (1,   3)  a r e   t h e   c l o s e s t   pa i r s   o f  po i n t s .   D 1 4 D 2 4 D 3 4 D 4 4 D 1 3 D 2 3 D 3 3 D 4 3 D 1 2 D 2 2 D 3 2 D 4 2 D 1 1 D 2 1 D 3 1 D 4 1 D 1 4 D 2 4 D 3 4 D 4 4 D 1 3 D 2 3 D 3 3 D 4 3 D 1 2 D 2 2 D 3 2 D 4 2 D 1 1 D 2 1 D 3 1 D 4 1 5 4 0 . 6 1 . 2 2 . 1 3 . 1 3 0 . 4 1 . 1 2 . 0 3 . 0 2 1 . 4 1 . 7 2 . 4 3 . 3 1 2 . 4 2 . 6 3 . 1 3 . 8 1 2 3 4 5 5 4 0 . 6 1 . 2 2 . 1 3 . 1 3 0 . 4 1 . 1 2 . 0 3 . 0 2 1 . 4 1 . 7 2 . 4 3 . 3 1 2 . 4 2 . 6 3 . 1 3 . 8 1 2 3 4 5 5 4 0 . 6 1 . 2 2 . 1 3 . 1 3 0 . 4 1 . 1 2 . 0 3 . 0 2 1 . 4 1 . 7 2 . 4 3 . 3 1 2 . 4 2 . 6 3 . 1 3 . 8 1 2 3 4 5 5 4 0 . 6 1 . 2 2 . 1 3 . 1 3 0 . 4 1 . 1 2 . 0 3 . 0 2 1 . 4 1 . 7 2 . 4 3 . 3 1 2 . 4 2 . 6 3 . 1 3 . 8 1 2 3 4 5 Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i     IS S N :   2502 - 4752       Modi f i e d  br u t e   f or c e   al gor i t hm   t o  s o l v e   t he   c l os e s t   pa i r   o f   po i nt s   pr obl e m   bas e d   on  . . . .   ( R how e l   M .   D e l l os a)   1633   3.   R ES U LTS   A N D   A N A L Y S I S   T h e   pr o po s e d  a l go r i t hm   w a s   e xe c ut e d  w i t h   t h e   us e   of  t h e   J a v a   pr o gra m m i ng  l a ngua ge .   P o i n t   R   (1. 3 ,   2. 2)  w a s   us e d  a s   t h e   r e f e r e n c e   po i nt   (R )  a n d  100  po i nt s   { (1,   1) , . . (1 ,   10) ,   (2 ,   1) . . (2 ,   10) …(10 , 1) . . ( 10,   10)  s a m pl e s   w e r e   us e d  a s   t h e   s e t   o f   po i n t s   (P ).   T h e s e   r e f e r e n c e   po i n t s   (R )  a n d  t h e   s a m pl e   s e t   o f   po i n t s   (P )   w e r e   us e d  t o   de m o n s t ra t e   h o w   t h e   p r o po s e d  a l go ri t hm   w o r ks .     3. 1 .       C o m p u tati o n   o f  D i s tan c e   In p ut     :   R e fe r e n c e   P o i nt   { R (1. 3,   2 . 2)}   a n d   t h e   s e t   o f   100  po i n t s   { (1,   1). . (1 0,   10)}     O ut put     :   D i s t a n c e s   b e t w e e n   { R (1. 3,   2 . 2)}   a n d   t h e   s e t   o f   100  po i n t s   T a b l e   1  s h o w s   t h e   s um m a r y   of   c o m put e d  di s t a n c e s   of   c o o r di n a t e s - m a p .   A   10x10  c o o r di n a t e s - m a p   gri d  w a s   us e d  t o   pr e s e n t   t h e   c o m put e d  di s t a n c e s   be t w e e n   t he   r e f e r e n c e   po i n t   a nd  t h e   s e t   o f   p o i n t s .   F i gu r e   11  s h o w s   t h a t   t h e   m i n i m u m   d i s t a n c e   i s   t h e   d i s t a n c e   l o c a t e d  a t   P (1,   2)  w hi c h  i s   e qui v a l e n t   t o   0. 4 .   H e n c e ,   t h e   c l o s e s t   pa i r  o f   po i n t s   i s   R (1 . 3,   2 . 2)  a n d   P (1 ,   2 ).       T a b l e   1 .   S u m m a r y   of   Co m put e d  D i s t a n c e   o f   Coo r di n a t e - M a p   7 . 8   7 . 8   8 . 0   8 . 3   8 . 6   9 . 1   9 . 7   1 0 . 3   1 1 . 0   1 1 . 7   6 . 8   6 . 8   7 . 0   7 . 3   7 . 7   8 . 3   8 . 9   9 . 5   1 0 . 3   1 1 . 0   5 . 8   5 . 8   6 . 0   6 . 4   6 . 9   7 . 5   8 . 1   8 . 9   9 . 6   1 0 . 5   4 . 8   4 . 9   5 . 1   5 . 5   6 . 1   6 . 7   7 . 5   8 . 2   9 . 1   9 . 9   3 . 8   3 . 9   4 . 2   4 . 7   5 . 3   6 . 0   6 . 9   7 . 7   8 . 6   9 . 5   2 . 8   2 . 9   3 . 3   3 . 9   4 . 6   5 . 5   6 . 4   7 . 3   8 . 2   9 . 1   1 . 8   1 . 9   2 . 5   3 . 2   4 . 1   5 . 0   6 . 0   6 . 9   7 . 9   8 . 9   0 . 9   1 . 1   1 . 9   2 . 8   3 . 8   4 . 8   5 . 8   6 . 7   7 . 7   8 . 7   0 . 4   0 . 7   1 . 7   2 . 7   3 . 7   4 . 7   5 . 7   6 . 7   7 . 7   8 . 7   1 . 2   1 . 4   2 . 1   3 . 0   3 . 9   4 . 9   5 . 8   6 . 8   7 . 8   8 . 8       3. 2 .       D e te r m i n ati o n   o f  C l o s e s t  P o i n t  to   th e   R e f e r e n c e   P o i n t   In p ut     :   D i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i nt   R ( 1 . 3,   2 . 2)   a n d   100   s e t   o f   po i n t s .       O ut put     :   Cl o s e s t   po i n t   P (x,   y ).           F i gu r e   10 .  S t e ps   o f   E xe c ut i o n   P r o c e s s   dur i ng  t h e   D e t e r m i n a t i o n   o f   Cl o s e s t   P o i n t           F i gu r e   11 .  S u m m a r y   of   E xe c ut i o n   P r o c e s s   duri n g   t h e   D e t e r m i n a t i o n  o f   Cl o s e s t   P o i n t   7 . 8 7 . 8 8 . 0 8 . 3 8 . 6 9 . 1 9 . 7 1 0 . 3 1 1 . 0 1 1 . 7 6 . 8 6 . 8 7 . 0 7 . 3 7 . 7 8 . 3 8 . 9 9 . 5 1 0 . 3 1 1 . 0 5 . 8 5 . 8 6 . 0 6 . 4 6 . 9 7 . 5 8 . 1 8 . 9 9 . 6 1 0 . 5 4 . 8 4 . 9 5 . 1 5 . 5 6 . 1 6 . 7 7 . 5 8 . 2 9 . 1 9 . 9 3 . 8 3 . 9 4 . 2 4 . 7 5 . 3 6 . 0 6 . 9 7 . 7 8 . 6 9 . 5 2 . 8 2 . 9 3 . 3 3 . 9 4 . 6 5 . 5 6 . 4 7 . 3 8 . 2 9 . 1 1 . 8 1 . 9 2 . 5 3 . 2 4 . 1 5 . 0 6 . 0 6 . 9 7 . 9 8 . 9 0 . 9 1 . 1 1 . 9 2 . 8 3 . 8 4 . 8 5 . 8 6 . 7 7 . 7 8 . 7 0 . 4 0 . 7 1 . 7 2 . 7 3 . 7 4 . 7 5 . 7 6 . 7 7 . 7 8 . 7 1 . 2 1 . 4 2 . 1 3 . 0 3 . 9 4 . 9 5 . 8 6 . 8 7 . 8 8 . 8 7 . 8 7 . 8 8 . 0 8 . 3 8 . 6 9 . 1 9 . 7 1 0 . 3 1 1 . 0 1 1 . 7 6 . 8 6 . 8 7 . 0 7 . 3 7 . 7 8 . 3 8 . 9 9 . 5 1 0 . 3 1 1 . 0 5 . 8 5 . 8 6 . 0 6 . 4 6 . 9 7 . 5 8 . 1 8 . 9 9 . 6 1 0 . 5 4 . 8 4 . 9 5 . 1 5 . 5 6 . 1 6 . 7 7 . 5 8 . 2 9 . 1 9 . 9 3 . 8 3 . 9 4 . 2 4 . 7 5 . 3 6 . 0 6 . 9 7 . 7 8 . 6 9 . 5 2 . 8 2 . 9 3 . 3 3 . 9 4 . 6 5 . 5 6 . 4 7 . 3 8 . 2 9 . 1 1 . 8 1 . 9 2 . 5 3 . 2 4 . 1 5 . 0 6 . 0 6 . 9 7 . 9 8 . 9 0 . 9 1 . 1 1 . 9 2 . 8 3 . 8 4 . 8 5 . 8 6 . 7 7 . 7 8 . 7 0 . 4 0 . 7 1 . 7 2 . 7 3 . 7 4 . 7 5 . 7 6 . 7 7 . 7 8 . 7 1 . 2 1 . 4 2 . 1 3 . 0 3 . 9 4 . 9 5 . 8 6 . 8 7 . 8 8 . 8 Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   3 ,  S e pt e m b e r   2 019   :     1 6 2 9   -   1 6 3 6   1634   3. 3 .       D e r i v ati o n   o f  th e   N u m b e r   o f  C o m p ar i s on s   o f  th e   P r o p o s e d   C P P   A l go r i th m   T h e   b r ut e   f o r c e   m e t h o d  c o m pa r e s   a l l   t h e   d i s t a n c e s   b e t w e e n   e a c h   p a i r  o f   p o i n t s   w h i l e   t h e   d i v i de - a n d - c o n que r   a l go ri t hm s   di v i de   t h e   s e t   of   di s t a n c e s   i nt o   t w o   a n d   c o m pa r e   a l l   t h e   di s t a n c e s   b e t w e e n   e a c h   p a i r   o f  po i n t s   o f   e a c h   di v i s i o n.   A ppl y i n g  e qua t i o n   (1)  o f   t h e   b r ut e   f o r c e   m e t h o d  a n d  di v i de - a n d - c o n que r   f o r   100  di s t a n c e s   t o   be   c o m pa r e d  r e s ul t e d  i n   T C  =  4950  an d  T C  =  2450 ,   r e s pe c t i v e l y .   In   t h e   p r o po s e d  CP P   a l go ri t hm ,   t h e   n u m b e r   o f   c o m pa r i s o n s   o nl y   de p e n ds   o n   t h e   n u m b e r   o f   s c h e m a t i c   s t e ps .   T h e   e qua t i o n   (2 )  i s   de r i v e d  t o   c o m put e   f o r   t h e   n u m b e r   o f   c o m pa r i s o n s :        =   ( ( − 1 ) 2 )   (2)     w h e r e :   K u    -   T h e   n um b e r  o f   c o m pa r i s o n  o f   t h e   p r o po s e d  CP P   a l go ri t hm   A     -   N um b e r  o f   s c h e m a t i c   s t e ps     n    -   T o t a l   num b e r  o f   di s t a n c e s   t o   b e   c o m pa r e d   A ppl y i n g  t h e   e qua t i o n   (2) ,   t h e   num b e r   o f   c o m pa r i s o n s   o f   t h e   p r o po s e d   CP P   a l go r i t hm   i s   Ku   =  60   w i t h  n   =   4  a n d   t h e   w o r s t   c a s e   v a l ue   o f   A   =   10   f o r   100   d i s t a n c e s   v a l ue .     3. 4 .       D at a  o n   th e   C o m p ar i s o n s   o f  o th e r   N u m b e r   o f  D i s ta n c e s     T a b l e   2  s h o w s   t h e   pr e s e n t a t i o n   o f   t h e   n u m b e r   o f  c o m pa ri s o n s   b e t w e e n   t h e   b r u t e   fo r c e ,   di v i de - a nd - c o n que r   a l go ri t hm   a nd  t h e   p r o po s e d  CP P   a l go r i t h m   us i n g  1 0 0,   10 , 000  a n d  1 , 000 , 00 0  di s t a n c e s ,   r e s pe c t i v e l y .   T o   de t e r m i n e   t h e   n u m b e r   o f   c o m pa r i s o n s   o f   t h e   d i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   a n d   s e t   o f   p o i n t s   f o r   b r ut e   f o r c e   a n d  di v i de - a n d - c o n que r   a l go r i t h m ,   t h e   e qua t i o n   ( 1)  w a s   us e d.   M o r e ove r ,   t o   de t e rm i n e   t h e   n u m b e r   of   c o m pa r i s o n s   o f   t h e   d i s t a n c e s   b e t w e e n   t h e   r e f e r e n c e   po i n t   a n d   s e t   o f   po i n t s   f o r   t h e   p r o po s e d  CP P   a l go ri t hm ,   t h e   e qua t i o n   (2)  w a s   us e d.   In   a ddi t i o n,   t h e   p r o po s e d  CP P   a l go r i t hm   us e d  10x10,   100x 100  a n d   1000x100 0  c o o r di n a t e s - m a p   g ri d  a n d   c o n s i de r e d   t h e   w o r s t   c a s e   v a l ue   o f   s c h e m a t i c   s t e ps   (A )  o f   10,   10 0  a n d   1000  r e s pe c t i v e l y .       T a b l e   2 .   N u m b e r   o f   Co m pa r i s o n s   o f   B r ut e   F o r c e   M e t h o d  a n d   t h e   P r o po s e d  CP P   N u m b e r   o f  D i s t a n c e s   t o   b e   C o m p a re d   Bru t e   F o rc e   M e t h o d   (N u m b er   o f  Co m p a r i s o n s )   D i v i d e - a n d - c o n q u e r   A l g o ri t h m   (N u m b e r   o f  C o m p a ri s o n s )   P ro p o s e d   CP P   a l g o r i t h m   (N u m b e r   o f  C o m p a ri s o n s )   W i t h   A = 1 0 ,   1 0 0 ,   1 0 0 0   re s p e c t i v e l y   100   4 , 9 5 0   2 , 4 5 0   60   1 0 , 0 0 0   4 9 , 9 9 5 , 0 0 0   2 4 , 9 9 5 , 0 0 0   600   1 , 0 0 0 , 0 0 0 . 0 0   4 . 9 9   x 1 0 11   2 . 4 4   x 1 0 11   6 , 0 0 0       4.   C O N C LU S I O N   T h e   m o di f i e d  b r ut e   f o r c e   a l go r i t h m   i s   t h e   p r o po s e d  a l go r i t hm   f o r   s o l v i n g  t h e   CP P   pr o b l e m .   T h e   pr o po s e d  a l go r i t h m   i s   s i m pl e   a n d  e a s y   t o   fo l l ow .   T h e   e xpe r i m e n t   r e s ul t s   s h o w e d  t ha t   t h e   n um b e r   o f  c o m pa ri s o n s   of   t h e   pr o po s e d  CP P   a l go r i t hm   i s   l e s s   t ha n   t h e   b r ut e   fo r c e   m e t h o d  a nd  t h e   di v i de - a n d - c o n que r   a l go ri t hm .   M o r e ov e r ,   t h e   pr o po s e d  CP P   a l go r i t hm   i s   e ff i c i e nt   i n   t e r m s   o f   t h e   n um b e r   o f   c o m pa r i s o n s   a s   pr o v e n   by   t h e   e xpe r i m e nt s   of   di ff e r e n t   s e t s   of   c o m put e d  di s t a n c e s .   T h e   p r o po s e d  a l go r i t hm   m a y   be   i m p l e m e nt e d  o n  c o o r di na t e   b a s e d  a p pl i c a t i o n s   l i ke   po s i t i o n   e s t i m a t i o n  a nd  s i m i l a ri t y   m a t c h i ng  t o   f ur t h e r   t e s t   i t s   f u n c t i o na l i t i e s .       A C K N O WL ED G E M EN TS   T h e   a ut h o r s   w o ul d  l i ke   t o   t h a n k  t h e i r   f a m i l y ,   l o ve d  o n e s ,   t h e   Co m m i s s i o n   o n   H i gh e r   E duc a t i o n ,   T e c hn o l o gi c a l   I n s t i t u t e   of   t h e   P h i l i pp i n e s - Q ue z o n   Ci t y ,   M a n ue l   L .   Q ue z o n   U n i v e r s i t y   a n d  A s i a   T e c hn o l o gi c a l   S c h o o l   of   S c i e n c e   a n d   A r t s   f o r   b e i n g  t h e   i n s pi ra t i o n s   o n   t h i s   r e s e a r c h   e n de a v o r .       R EF ER EN C ES   [ 1]   E .   D a l ki l i ç   a nd   S .   E r ,   “ A   s i m pl e s t   f as t   al gor i t hm   f or   t he   c l os e s t -   pai r   pr o bl e m   us i ng  s o r t e d  pr oj e c t i o ns   o n  m ul t i - di m e ns i ons , ”   P r o c e e di ng s   o f   t he   28t h  I nt e r n a t i o na l   S y m po s i um   o n   C o m put e r   a nd  I nf o r m a t i o n  S c i e nc e s   S pr i n g e r ,   pp.   23 - 34 ,   201 3.     [ 2]   J .   C .   P e r e i r a   a nd  F .   G .   L o bo ,   “ A n  o pt i m i z e d  d i v i de - a nd - c o nque r   a l g o r i t hm   f o r   t he   c l o s e s t - pa i r   p r o bl e m   i n  t he   p l a na r   c a s e , ”   J our nal   o f   C om pu t e r   S c i e nc e   and   T e c hno l og y ,   v o l .   27 ,   p p.   8 91 - 896,   2 012 .   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i     IS S N :   2502 - 4752       Modi f i e d  br u t e   f or c e   al gor i t hm   t o  s o l v e   t he   c l os e s t   pa i r   o f   po i nt s   pr obl e m   bas e d   on  . . . .   ( R how e l   M .   D e l l os a)   1635   [ 3]   W .   H ua ng ,   “ W al k i e l ok i e :   Se ns i ng  R e l at i v e   P os i t i ons   o f   Sur r ound i ng  P r e s e nt e r s   by   A c ous t i c   Si g na l s , ”   i n   P r o c e e di ng s   o f   t he   2016  A C M   I nt e r na t i o na l   J o i n t   C o nf e r e nc e   o n  P e r v a s i v e   a nd  U bi q ui t o us   C o m put i ng ,     pp.   43 9 - 450,   2 016 .   [ 4]   M .   S ha m o s   a nd   D .   H o e y ,   “ C l o s e s t   P o i n t   P r o bl e m , ”   16 t h  A nnua l   S y m pos i u m   on  F ound at i on s   o f   C om pu t e r   Sc i e nc e   ( s f c s   19 75) ,   O c t   1 975 .   [ 5]   Y .   Z ho u,   e t   a l . ,   “ A n  i m pr o v e d  a l g o r i t hm   a bo u t   t he   c l o s e s t   pa i r   o f   po i nt s   o n  pl a ne   s e t , ”   C om put e r   R e s e ar c h  a nd   D e v e l opm e nt ,   v o l .   35 ,   pp .   957 - 960 ,   199 8.   [ 6]   Q .   G e ,   e t   a l . ,   “ A n  I m pr ov e d  A l go r i t hm   f o r   F i n di ng   t h e   C l o s e s t   P a i r   o f   P o i nt s , ”   J ou r na l   of   C om p ut e r   Sc i e nc e   and   T e c hnol o gy ,   v o l .   21 ,   pp .   2 7 - 31,   J a n   200 6.   [ 7]   J .   J i a ng   a nd   G i l l e s pi e ,   “ E ng i ne e r i ng   t he   d i v i d e - a nd - c o nque r   c l o s e s t   pa i r   a l g o r i t hm , ”  J our n al   o f   C om pu t e r   Sc i e nc e   and  T e c hno l ogy ,   v o l .   2 2,   pp .   532 - 54 0,   20 07.   [ 8]   Y .   Z ho u  a nd  H .   Y u ,   “ A n  E f f i c i e nt   C om p ar i s o n - B a s e d  D e t e r m i n i s t i c   A l gor i t hm   t o  So l v e   t he   C l o s e s t   P ai r   P r obl e m , ”   2015  8 t h  I nt e r n a t i o na l   C o nf e r e nc e   o n  I nt e l l i g e nt   C o m put a t i o n  T e c hno l o gy   a nd  A ut o m a t i o n  ( I C I C T A ) ,   N a nc ha ng ,   pp.   14 5 - 148,   2 015 .   [ 9]   Y .   W a ng ,   e t   al . ,   “ W ar pM a p:   A c c ur a t e   and  E f fi c i e nt   I ndo or   L oc at i o n  by   D y nam i c   W ar pi ng  i n  Se que nc e - T y pe   R adi o - M ap , ”   2016  13 t h  A nnua l   I E E E   I nt e r na t i o na l   C o nf e r e nc e   o n  S e ns i ng ,   C o m m uni c a t i o n,   a nd  N e t w o r k i ng   ( S E C O N ) ,   pp.   1 - 9,   2 016 .   [ 10]   A .   C .   Y a o ,   “ L o w e r   bo unds   f o r   a l g e br a i c   c o m put a t i o n  t r e e s   w i t h  i n t e g e r   i n put s , ”   S I A M   J ou r na l   on  C om pu t i n g,   v o l .   20,   pp .   655 - 66 8,   19 91.   [ 11]   J .   L .   B e n t l e y   a nd  M .   I .   S ha m o s ,   “ D i v i de - and - c onque r   i n  m ul t i di m e ns i o na l   s pa c e , ”   i n  P r o c e e di ng s   o f   e i   g ht h  a nnu a l   A C M   S y m po s i um   o n  T he o r y   o f   C o m put i ng   ( S T O C ) ,   N e w   Y o r k,   N Y ,   U S A ,   pp .   2 20 - 230 ,  1976 .   [ 12]   M.   Z .   K a r i m   a nd  N .   A kt e r ,   “ O p t i m um   p a r t i t i o n  pa r a m e t e r   o f   di v i d e - a nd  c o nque r   a l g o r i t hm   f o r   s o l v i ng   c l o s e s t - pa i r   pr o bl e m , ”   I n t e r na t i ona l   J ou r na l   of   C om p ut e r   Sc i e nc e   &   I nf or m a t i o n  T e c h n ol o gy ,   v o l .   3,   p p. 2 11 - 219 ,   2011 .   [ 13]   K .   H i n r i c hs ,   e t   a l . ,   “ P l a ne - s w e e p  s o l v e s   t he   c l o s e s t   pa i r   pr o bl e m   e l e g a n t l y , ”   I n f or m at i on  P r oc e s s i n g  L e t t e r s ,   v o l .   26,   pp .   255 - 26 1,   19 88.   [ 14]   C .   S c hw a r z ,   e t   a l . ,   “ A n  o pt i m al   al gor i t hm   f o r   t he   on - l i ne   c l os e s t - p ai r   p r ob l e m , ”   i n  P r o c e e di ng s   o f   t he   8 t h  A nnua l   S y m po s i um   o n  C o m put a t i o na l   G e o m e t r y ,   A C M   P r e s s ,   N e w   Y o r k,   pp.   33 0 - 336 ,  1 992 .   [ 15]   X .   Z ha ng ,   e t   a l . ,   “ T E A M :   e ffi c i e nt   t w o - l o c us   e pi s t a s i s   t e s t s   i n  hum a n  g e no m e - w i de   a s s o c i a t i o n  s t ud , ”   B i o i nf or m a t i c s   ( O x f o r d ,   E ngl and) ,  v o l .   26 ,   p p.   21 7 - 227 ,   J un   201 0.   [ 16]   X .   Z ha ng ,   e t   a l . ,   “ F as t a nov a :   an  e ffi c i e nt   a l go r i t hm   f or   ge nom e - w i de   as s oc i a t i on  s t ud y , ”   i n  P r o c .   14t h  A C M   S I G K D D   i nt e r na t i o na l   c o nf e r e nc e   o n  K no w l e dg e   di s c o v e r y   a nd  da t a   m i n i ng   ( K D D ) ,   L a s   V e g a s ,   N e v a da ,   U S A ,   p p.   821 - 829 ,  2008 .   [ 17]   R .   P a t ur i ,   e t   a l . ,   “ T he   l i gh t   bu l b  pr obl e m , ”   i n  P r o c .   2nd  A nnu.   W o r ks ho p  o n  C o m put .   L e a r n i ng   T he o r y ,   S a n  M a t e o ,   C A ,   pp.   26 1 - 268 ,  1 989 .   [ 18]   M .   S .   C ha r i ka r ,   “ Si m i l ar i t y   e s t i m a t i on  t e c hn i que s   f r om   r oun di ng  a l gor i t hm s , ”   P r o c .   A C M   S y m p o s i um   o n  T he o r y   o f   C om put i ng   ( S T O C ) ,   200 2 .   [ 19]   M .   R a b i n ,   “ P r o ba bi l i s t i c   A l go r i t hm s ,   A l go r i t hm s   a nd  C o m pl e xi t y ,   “ R e c e nt   R e s ul t s   and  N e w   D i r e c t i o ns ,   A c ade m i c   P r e s s ,   pp .   21 - 39 ,   1976 .   [ 20]   A .   M ue e n ,   e t   a l . ,   “ E x ac t   D i s c o v e r y   of   T i m e   Se r i e s   M ot i f s , ”   S I A M   I nt e r na t i o na l   C o nf e r e nc e   o n  D a t a   M i n i ng   ( S D M )   2009 .   [ 21]   P .   B e a u do i n,   e t   a l . ,   “ M o t i o n - M o t i f   G r a ph s , ”  Sy m po s i um   o n  C om pu t e r   A ni m at i on ,   2008 .   [ 22]   B .   C hi u ,   e t   a l . ,   “ P r obab i l i s t i c   di s c o v e r y   of   t i m e   s e r i e s   m ot i f s ,”   P r o c .   of   t he   9t h  I nt e r na t i o na l   C o nf e r e nc e   o n  K no w l e dg e   D i s c o v e r y   a nd  D a t a   m i n i ng   ( K D D ) ,   p p.   49 3 - 498 ,   2 003 .   [ 23]   T .   G uy e t ,   e t   a l . ,   “ K no w l e dg e   c o ns t r uc t i o n  f r o m   t i m e   s e r i e s   da t a   us i ng   a   c o l l a bo r a t i v e   e x pl o r a t i o n  s y s t e m , ”   J our nal   of   B i om e d i c a l   I n f or m at i c s ,   v o l .   40 ,   pp .   672 - 68 7 ,   20 07 .   [ 24]   J .   M e ng ,   e t   a l . ,   “ M i ni ng   m ot i f s   f r om   hum an   m o t i o n , ”   P r o c .   o f   E U R O G R A P H I C S ,   200 8.   [ 25]   D .   M i nne n,   e t   a l . ,   “ D i s c ov e r i ng  m u l t i v a r i at e   m ot i f s   us i ng  s ub s e que nc e   de ns i t y   e s t i m a t i o n  and  gr e e dy   m i x t ur e   l e ar ni ng , ”   P r o c .   2 2nd   C o nf e r e nc e   o n  A r t i fi c i a l   I nt e l l i g e nc e   ( A A A I 0 7) ,   2 007 .   [ 26]   M.   S .   R a hm a n,   e t   a l . ,   “ I ndoo r   po s i t i o ni ng   b y   L E D   v i s i bl e   l i g ht   c om m uni c a t i o n  a nd  i m a g e   s e ns o r s , ”   I nt e r n at i ona l   J our nal   o f   E l e c t r i c a l   a nd   C om pu t e r   E ngi ne e r i ng   ( I J E C E ) ,   v ol .   1 ,   2 011.       B I O G R A P H I ES   O F   A U T H O R S           R ho w e l   M .   D e l l o s a   o bt a i ne d  h i s   B a c he l o r   o f   S c i e nc e   de g r e e   i n  C o m put e r   E ng i n e e r i ng   f r o m   S a i n t   J o s e p h  I ns t i t ut e   o f   T e c hn o l o gy ,   P hi l i ppi ne s   i n  20 00 .   I n  2 002,   h e   o bt a i ne d  a   s e p a r a t e   B a c he l o r   o f   S c i e nc e   de g r e e   i n  E l e c t r o ni c s   a nd  C o m m uni c a t i o ns   E ng i ne e r i ng   f r o m   t he   s a m e   i ns t i t u t i o n .   H e   f i ni s he d  h i s   M a s t e r ’ s   de g r e e   i n  E ng i n e e r i ng   w i t h   s pe c i a l i z a t i o n  i n   C o m put e r   E ng i ne e r i ng   i n   200 7  f r o m   t he   U ni v e r s i t y   of   t he   C i t y   of   M a ni l a .   H e   i s   c ur r e nt l y   t a ki ng   up  D oc t o r   o f   E n g i ne e r i ng   w i t h  s pe c i a l i z a t i o n  i n  C o m put e r   E ng i ne e r i ng   f r o m   t he   T e c hno l o g i c a l   I ns t i t ut e   o f   t he   P h i l i p pi ne s   i n  Q u e z o n  C i t y ,   P hi l i ppi ne s .   H i s   r e s e a r c h  i nt e r e s t s   i nc l ud e   c o m put a t i o na l   g e o m e t r y ,   w i r e l e s s   s e n s o r   ne t w o r k s ,   s t a t i s t i c a l   a na l y s i s   a nd  c o m put e r   f o r e n s i c s .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   3 ,  S e pt e m b e r   2 019   :     1 6 2 9   -   1 6 3 6   1636     A r ne l   C .   F a j a r do   r e c e i v e d  h i s   B . S .   E l e c t r i c a l   E ng i ne e r i ng   de g r e e   i n  1 991  f r o m   t he   M a pú a   I ns t i t u t e   o f   T e c hn o l o gy   i n  I nt r a m u r o s ,   M a ni l a .   H e   o bt a i n e d  hi s   M . S .   C o m put e r   S c i e nc e   de g r e e   i n   1999  f r o m   D e   L a   S a l l e   U n i v e r s i t y   M a n i l a .   H e   o b t a i ne d   h i s   P h. D .   i n  C o m put e r   E ng i ne e r i ng   de g r e e   f r o m   H a n ba t   N a t i o na l   U n i v e r s i t y ,   D a e j e o n,   S o ut h   K o r e a   i n  2014 .   H e   i s   t he   S e ni o r   A s s i s t a n t   V i c e   P r e s i d e n t   a nd  R e s e a r c h  D i r e c t o r   o f   M a nue l   L .   Q ue z o n  U ni v e r s i t y   a nd  P r o f e s s o r i a l   l e c t u r e r   o f   v a r i o us   un i v e r s i t i e s   i n  t he   P h i l i p pi n e s .   H e   i s   a n  a u t ho r   o f   m o r e   t h a n  30   a r t i c l e s   i n  j o ur na l s   a nd  c o nf e r e nc e   p r o c e e di ng s .   H i s   r e s e a r c h  i n t e r e s t   i nc l ud e s   s pe e c h   r e c o g ni t i o n,   i m a g e   pr o c e s s i ng   a r t i f i c i a l   i n t e l l i g e nc e   a nd   e ng i n e e r i ng   e duc a t i o n .       R uj i   P .   M e d i na   i s   D e a n  o f   G r a d ua t e   P r o g r a m s   o f   t he   T e c hno l o g i c a l   I ns t i t ut e   o f   t he   P hi l i pp i ne s   i n   Q ue z o n  C i t y ,   P hi l i p pi n e s .   H e   r e c e i v e d  hi s   B . S .   C he m i c a l   E ng i ne e r i ng   de g r e e   f r o m   t he   U ni v e r s i t y   o f   t he   P hi l i pp i ne s   –   D i l i m a n ,   Q u e z o n  C i t y   i n  199 2.   H e   g r a dua t e d  s um m a   c um   l a ud e   f r o m   t he   M a pú a   I ns t i t u t e   o f   T e c hno l o gy   i n  I nt r a m ur o s ,   M a ni l a   i n   200 0  w i t h  a   M . S .   i n   E nv i r o nm e nt a l   E ng i ne e r i ng   de g r e e .   H e   ho l ds   a   P h . D .   i n  E nv i r o nm e nt a l   E ng i ne e r i ng   f r o m   t he   U ni v e r s i t y   o f   t he   P hi l i pp i ne s   w i t h  s a n dw i c h  p r o g r a m   a t   t h e   U ni v e r s i t y   o f   H o us t o n,   T e x a s .   H e   c o unt s   a m o ng   hi s   e xpe r t i s e   e nv i r o nm e n t a l   a nd  m a t he m a t i c a l   m o de l i ng ,   u r ba n  m i n i ng ,   a n d   na no m a t e r i a l s .   A pa r t   f r o m   hi s   a c t i v e   r o l e   i n  r e s e a r c h  a nd  g r a d ua t e   e ng i ne e r i ng   e duc a t i o n,   he   i s   a n  e xc e l l e n t   t e c hn i c a l   m e n t o r   w i t h  num e r o us   p ubl i c a t i o ns   unde r   hi s   na m e .       Evaluation Warning : The document was created with Spire.PDF for Python.